We present our approach for the CG:SHOP 2026 challenge. In this international challenge, the goal was to find a median triangulation for a set of triangulations in the parallel flip reconfiguration graph of all triangulations of an underlying point set. Our simulated-annealing-based approach makes use of two ingredients: a heuristic edge selection for approximating the parallel flip distance of two given triangulations, and a heuristic procedure to generate good initial triangulations.

This repository contains benchmark instances for (s,t)-max-flow/min-cut, which were submitted to the 13th DIMACS Implementation Challenge. The instances are derived from the bicriteria polygon aggregation problem, which is studied in the following publications: Bicriteria Shapes: Hierarchical Grouping and Aggregation of Polygons with an Efficient Graph-Cut Approach. Peter Rottmann, Anne Driemel, Herman Haverkort, Heiko Röglin, Jan-Henrik Haunert. In: ACM Transactions on Spatial Algorithms and Systems, vol. 11(1), ACM, pages 3:1--3:23, 2025. A Simpler Approach for Monotone Parametric Minimum Cut: Finding the Breakpoints in Order. Arne Beines, Michael Kaibel, Philip Mayer, Petra Mutzel, Jonas Sauer. In: Proceedings of the 27th Workshop on Algorithm Engineering and Experiments (ALENEX'25), SIAM, pages 29--41, 2025. Bicriteria Polygon Aggregation with Arbitrary Shapes. Lotte Blank, David Eppstein, Jan-Henrik Haunert, Herman Haverkort, Benedikt Kolbe, Philip Mayer, Petra Mutzel, Alexander Naumann, Jonas Sauer. To appear in: Proceedings of the 34th Annual European Symposium on Algorithms (ESA'26), Leibniz International Proceedings in Informatics, 2026. Background These instances are derived from a real-world application: polygon aggregation for map simplification. Given is a set $P$ of building footprints, represented as 2D polygons. The objective is to find a set $S$ of interior-disjoint representative regions, such that each polygon in $P$ is fully contained in a region of $S$. We are interested in a solution that minimizes the objective function $g_\alpha(S) = A(S) + \alpha \cdot P(S)$, where $A(S)$ and $P(S)$ are the total area and perimeter of the regions in $S$, respectively. The parameter $\alpha$ controls the trade-off between faithfulness to the input (represented by the area) and shape simplicity (represented by the perimeter). In a cartographic application, it can be thought of as the "zoom factor" -- the further we zoom out, the simpler we want the shapes to become. We distinguish between two variants of the problem, both for a fixed choice of $\alpha$: Subdivision-based: A subdivision $D$ of the plane (e.g., a constrained Delaunay triangulation) is supplied in advance, such that each polygon in $P$ appears as a cell of $D$. The solution must be constructed by selecting cells from $D$ to add to $P$. The problem is solved via a transformation to (s,t)-min-cut on an augmented geometric dual of $D$ (see any of the papers listed above for details). Unrestricted: No restrictions are made regarding the shape of $S$ -- the only conditions are that $P$ must be covered and that the objective function $g_\alpha(S)$ is minimized. Blank et al. show that in this variant, the polygons are connected by circular arcs of radius $\alpha$ that fulfill several other conditions. The arcs are chosen from a set of $O(n^2)$ candidates. The problem can then be solved optimally via a transformation to the subdivision-based case, where the subdivision $D$ is created by superimposing all $O(n^2)$ arcs. This yields a solution in polynomial time, although the subdivision is much more complex than the constrained Delaunay triangulation. The resulting instances have some similarities with grid-based computer vision max-flow instances, which are built using a similar geometric-dual construction: They are sparse and have short (s,t)-paths. However, unlike typical vision instances, they do not have a regular structure because they are derived from human settlement areas. Consequently, although all nodes (except for s and t) have low degrees, the degrees are not entirely uniform. For the unrestricted variant, the graph is highly detailed because it is derived from a geometric intersection process between many circular arcs. As a side note, a parametric version of the problem, where $\alpha$ is not fixed, has also been studied. Here, the objective is to find an optimal solution for every possible value of $\alpha$. Beines et al. show that, with an equivalent reformulation of the objective function $g_\alpha$, this is a monotone parametric min-cut problem. The instances in this dataset are not parametric, but parametric instances can be found here. Contents The dataset is split into two groups, depending on how the subdivision was built: triangulations: Using a constrained Delaunay triangulation, as proposed by Rottmann et al. The instances are cities of varying sizes (Bonn, Cologne, Berlin, Miami) and the entire German state of Saarland. For each instance, there are five copies, with the different $\alpha$ values 100, 500, 1000, 5000, and 25000. Note that the graph structure is the same for all copies; only the weights are different. arcs: Using the geometric intersection of the candidate arcs, as proposed by Blank et al. for the unrestricted variant. The instances represent the towns of Ahrem, Edendorf, Friesheim and Gerolstein in the German state of North Rhine-Westphalia. For each instance, there are four copies, with the different $\alpha$ values 100, 500, 1000, 5000. Note that for this variant, the graph size increases dramatically with $\alpha$. The arc capacities represent a weighted tradeoff between area and perimeter, measured in square decimeters (dm^2) and rounded to the nearest integer. The $\alpha$ parameter is also measured in decimeters. In the arcs instances, this corresponds to the radii of the circular arcs from which the subdivision is formed, e.g., $\alpha=5000$ represents arcs with radii of 500m. Data Sources Ahrem, Friesheim, Edendorf, Gerolstein, Bonn, Cologne: OpenStreetMap data from Geofabrik Saarland: OpenStreetMap data from Geofabrik Berlin, Miami: GHS-OBAT project Format The files follow the format from the first DIMACS implementation challenge. This is a text format in which each line is prefixed with a character that specifies the type of line. Lines starting with c are comments and should be ignored. The first non-comment line is the problem line: p max NODES ARCS Here, max is the problem type (max-flow/min-cut), NODES is the number of nodes in the network, and ARCS is the number of directed arcs. This is followed by two node descriptor lines:n IDT tn IDS s Here, IDT is the id of the sink node and IDS is the id of the source node. Note that in this format, node ids start at 1. Finally, there is an arc descriptor line for every directed arc in the network: a SRC DST C This specifies an arc from node SRC to DST with capacity C. Capacities with values of int32_max or more should be interpreted as infinite. Note that the format does not require that a reverse arc exists for every directed arc. If reverse arcs are required by your algorithm, you must ensure that missing arcs are added with capacity 0. Credits and Contact This dataset was created by two research groups at the University of Bonn: the geoinformation group headed by Prof. Dr. Jan-Henrik Haunert and the Computational Analytics group headed by Prof. Dr. Petra Mutzel. It is released under the MIT license. When using it, please cite the publications listed above. If you want to report problems or give feedback on the dataset, please contact Jonas Sauer ([email protected]).

We present parametric breadth-first search (PBFS), a new algorithm for solving the parametric minimum cut problem in a network with source-sink-monotone capacities. The objective is to find the set of breakpoints, i.e., the points at which the minimum cut changes. It is well known that this problem can be solved in the same asymptotic runtime as the static minimum cut problem. However, existing algorithms that achieve this runtime bound involve fairly complicated steps that are inefficient in practice. PBFS uses a simpler approach that discovers the breakpoints in ascending order, which allows it to achieve the desired runtime bound while still performing well in practice. We evaluate our algorithm on benchmark instances from polygon aggregation and computer vision. Polygon aggregation was recently proposed as an application for parametric minimum cut, but the monotonicity property has not been exploited fully. PBFS outperforms the state of the art on most benchmark instances, usually by a factor of 2–3. It is particularly strong on instances with many breakpoints, which is the case for polygon aggregation. Compared to the existing min-cut-based approach for polygon aggregation, PBFS scales much better with the instance size. On large instances with millions of vertices, it is able to compute all breakpoints in a matter of seconds.

Background: Anecdotal evidence suggests that software applications are usually implemented using a combination of (programming) languages. Aim: We want to provide empirical evidence on the phenomenon of multi-language programming. Methods: We use data mining of 1150 open source projects selected for diversity from a public repository to a) investigate the projects for number and type of languages found and the relative sizes of the languages; b) report on associations between the number of languages found and the size, age, number of contributors, and number of commits of a project using a (Quasi-)Poisson regression model, and c) discuss concrete associations between the general-purpose languages and domain-specific languages found using frequent item set mining. Results: We found a) a mean number of 5 languages per project with a clearly dominant main general-purpose language and 5 often-used DSL types, b) a significant influence of the size, number of commits, and the main language on the number of languages as well as no significant influence of age and number of contributors, and c) three language ecosystems grouped around XML, Shell/Make, and HTML/CSS. Conclusions: Multi-language programming seems to be common in open-source projects and is a factor which must be dealt with in tooling and when assessing development and maintenance of such software systems.

The term Cross-Language Linking refers to the ability to specify, locate, navigate, and keep intact the connections between artifacts defined in different programming languages used for building one software application. Although understanding cross-language links and keeping them intact during development and maintenance activities is an important productivity issue, there has been little research on understanding the characteristics of such connections. We have thus built a theory from case studies, specifically, three theory-selected Java cross-language frameworks, each of which links artifacts written in the Java programming language to artifacts written in a declarative, framework-specific domain specific language. Our main contribution is to identify, from these experiences, common patterns of cross-language linking in the domain of Java frameworks with DSLs, which besides their informative nature can also be seen as requirements for designing and building a linking language and tooling infrastructure.

With the days of the lone coder long gone, it is critical in our education of young computer scientists to lay particular emphasis on the “softer” spots of software development: How to organize a development process, how to deal with teams of software engineers with different skills and motivations, and how to produce outstanding software despite hard deadlines and (ideally) a 40-hour-week. In this paper, we report on the setup, execution, and results of two software development labs with a specific focus on agile methodologies conducted in 2010 and 2011 at our university. Not only are agile methods widespread in practice today; with their focus on human interaction and work-life balance, we believe that experiencing a full agile product development cycle in the risk-free academic environment is a benefit not only for our students' technical skills, but to their social skills as well.

Software composed of artifacts written in multiple (programming) languages is pervasive in today's enterprise, desktop, and mobile applications. Since they form one system, artifacts from different languages reference one another, thus creating what we call semantic cross-language links. By their very nature, such links are out of scope of the individual programming language, they are ignored by most language-specific tools and are often only established -- and checked for errors -- at runtime. This is unfortunate since it requires additional testing, leads to brittle code, and lessens maintainability. In this paper, we advocate a generic approach to understanding, analyzing and refactoring cross-language code by explicitly specifying and exploiting semantic links with the aim of giving developers the same amount of control over and confidence in multi-language programs they have for single-language code today.

Service-Oriented Architectures (SOAs) have become an important cornerstone of the development of enterprise-scale software applications. Although a range of domain-specific languages and standards are available for dealing with such architectures, model-driven approaches starting from models written in an established modelling language like UML and including the ability for model transformation (in particular, for code generation) are still in their infancy. In this paper, we show (1) how our UML-based domain-specific language for working with SOA artefacts, UML4SOA, can be used for modelling service orchestrations, and (2) how to exploit so-designed models in the MDD4SOA approach to generate code in multiple languages, among them BPEL and WSDL, Java, and the formal language Jolie. We use a case study for illustrating this approach. Our main contributions are an easy-to-use, conservative extension to the UML2 for modelling service orchestrations on a high level of abstraction, and a fully automated, model-driven approach for transforming these orchestrations down to code.

Developing service compositions, using multiple standards and implementation techniques, typically involves specifying service characteristics in different languages and tools. Examples are defining service composition behaviour, in the form of the business process execution language for Web services (WS-BPEL) and a global service choreography policy, in the form of the Web service choreography description language (WS-CDL). Whilst there have been a number of model-based analysis tools reported, there is a lack of integration with development environments to support analysis of these different service artifacts. In this paper we present a short history of some of the analysis tools reported, discuss an appropriate criteria of accessible integrated development with analysis features and provide an example approach, called "service engineer" using our tools and integration work. The approach is supported by an integrated service tool-chain development environment known as the SENSORIA development environment. The aim is to provide an accessible, rigorous approach to analysing service compositions but with a simple, clearly defined interface in an integrated development environment.