Publications of Christopher Weyand

2023 [ nach oben ]

Böther, Maximilian; Kißig, Otto; Weyand, Christopher Efficiently Computing Directed Minimum Spanning TreesSIAM Symposium on Algorithm Engineering and Experiments (ALENEX) 2023: 86–95
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Computing a directed minimum spanning tree, called arborescence, is a fundamental algorithmic problem, although not as common as its undirected counterpart. In 1967, Edmonds discussed an elegant solution. It was refined to run in O(min(n2, m log n)) by Tarjan which is optimal for very dense and very sparse graphs. Gabow et al. gave a version of Edmonds’ algorithm that runs in O(n log n +m), thus asymptotically beating the Tarjan variant in the regime between sparse and dense. Despite the attention the problem received theoretically, there exists, to the best of our knowledge, no empirical evaluation of either of these algorithms. In fact, the version by Gabow et al. has never been implemented and, aside from coding competitions, all readily available Tarjan implementations run in O(n2). In this paper, we provide the first implementation of the version by Gabow et al. as well as five variants of Tarjan’s version with different underlying data structures. We evaluate these algorithms and existing solvers on a large set of real-world and random graphs.
@inproceedings{bother2023efficiently, abstract = {Computing a directed minimum spanning tree, called arborescence, is a fundamental algorithmic problem, although not as common as its undirected counterpart. In 1967, Edmonds discussed an elegant solution. It was refined to run in O(min(n2, m log n)) by Tarjan which is optimal for very dense and very sparse graphs. Gabow et al. gave a version of Edmonds’ algorithm that runs in O(n log n +m), thus asymptotically beating the Tarjan variant in the regime between sparse and dense. Despite the attention the problem received theoretically, there exists, to the best of our knowledge, no empirical evaluation of either of these algorithms. In fact, the version by Gabow et al. has never been implemented and, aside from coding competitions, all readily available Tarjan implementations run in O(n2). In this paper, we provide the first implementation of the version by Gabow et al. as well as five variants of Tarjan’s version with different underlying data structures. We evaluate these algorithms and existing solvers on a large set of real-world and random graphs.}, author = {Böther, Maximilian and Kißig, Otto and Weyand, Christopher}, booktitle = {SIAM Symposium on Algorithm Engineering and Experiments (ALENEX)}, keywords = {sys:relevantfor:ae alenex christopherweyand maximilianboether ottokissig year2023}, pages = {86–95}, title = {Efficiently Computing Directed Minimum Spanning Trees}, year = 2023 }

2022 [ nach oben ]

Bläsius, Thomas; Friedrich, Tobias; Stangl, David; Weyand, Christopher An Efficient Branch-and-Bound Solver for Hitting SetAlgorithm Engineering and Experiments (ALENEX) 2022
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The hitting set problem asks for a collection of sets over a universe \(U\) to find a minimum subset of \(U\) that intersects each of the given sets. It is NP-hard and equivalent to the problem set cover. We give a branch-and-bound algorithm to solve hitting set. Though it requires exponential time in the worst case, it can solve many practical instance from different domains in reasonable time. Our algorithm outperforms a modern ILP solver, the state-of-the-art for hitting set, by at least an order of magnitude on most instances.
@inproceedings{blasius2022efficient, abstract = {The hitting set problem asks for a collection of sets over a universe \(U\) to find a minimum subset of \(U\) that intersects each of the given sets. It is NP-hard and equivalent to the problem set cover. We give a branch-and-bound algorithm to solve hitting set. Though it requires exponential time in the worst case, it can solve many practical instance from different domains in reasonable time. Our algorithm outperforms a modern ILP solver, the state-of-the-art for hitting set, by at least an order of magnitude on most instances.}, author = {Bläsius, Thomas and Friedrich, Tobias and Stangl, David and Weyand, Christopher}, booktitle = {Algorithm Engineering and Experiments (ALENEX)}, keywords = {alenex christopherweyand davidstangl thomasblaesius tobiasfriedrich year2022}, title = {An Efficient Branch-and-Bound Solver for Hitting Set}, year = 2022 }

Bläsius, Thomas; Fischbeck, Philipp; Gottesbüren, Lars; Hamann, Michael; Heuer, Tobias; Spinner, Jonas; Weyand, Christopher; Wilhelm, Marcus A Branch-and-Bound Algorithm for Cluster EditingSymposium on Experimental Algorithms (SEA) 2022: 13:1–13:19
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The editing problem asks to transform a given graph into a disjoint union of cliques by inserting and deleting as few edges as possible. We describe and evaluate an exact branch-and-bound algorithm for cluster editing. For this, we introduce new reduction rules and adapt existing ones. Moreover, we generalize a known packing technique to obtain lower bounds and experimentally show that it contributes significantly to the performance of the solver. Our experiments further evaluate the effectiveness of the different reduction rules and examine the effects of structural properties of the input graph on solver performance. Our solver won the exact track of the 2021 PACE challenge.
@inproceedings{blasius2022branchandbound, abstract = {The editing problem asks to transform a given graph into a disjoint union of cliques by inserting and deleting as few edges as possible. We describe and evaluate an exact branch-and-bound algorithm for cluster editing. For this, we introduce new reduction rules and adapt existing ones. Moreover, we generalize a known packing technique to obtain lower bounds and experimentally show that it contributes significantly to the performance of the solver. Our experiments further evaluate the effectiveness of the different reduction rules and examine the effects of structural properties of the input graph on solver performance. Our solver won the exact track of the 2021 PACE challenge.}, author = {Bläsius, Thomas and Fischbeck, Philipp and Gottesbüren, Lars and Hamann, Michael and Heuer, Tobias and Spinner, Jonas and Weyand, Christopher and Wilhelm, Marcus}, booktitle = {Symposium on Experimental Algorithms (SEA)}, keywords = {christopherweyand jonasspinner larsgottesbueren marcuswilhelm michaelhamann philippfischbeck sea thomasblaesius tobiasheuer year2022}, pages = {13:1–13:19}, title = {A Branch-and-Bound Algorithm for Cluster Editing}, year = 2022 }

2021 [ nach oben ]

Bläsius, Thomas; Friedrich, Tobias; Weyand, Christopher Efficiently Computing Maximum Flows in Scale-Free NetworksEuropean Symposium on Algorithms (ESA) 2021: 21:1–21:14
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We study the maximum-flow/minimum-cut problem on scale-free networks, i.e., graphs whose degree distribution follows a power-law. We propose a simple algorithm that capitalizes on the fact that often only a small fraction of such a network is relevant for the flow. At its core, our algorithm augments Dinitz's algorithm with a balanced bidirectional search. Our experiments on a scale-free random network model indicate sublinear run time. On scale-free real-world networks, we outperform the commonly used highest-label Push-Relabel implementation by up to two orders of magnitude. Compared to Dinitz's original algorithm, our modifications reduce the search space, e.g., by a factor of 275 on an autonomous systems graph. Beyond these good run times, our algorithm has an additional advantage compared to Push-Relabel. The latter computes a preflow, which makes the extraction of a minimum cut potentially more difficult. This is relevant, for example, for the computation of Gomory-Hu trees. On a social network with 70000 nodes, our algorithm computes the Gomory-Hu tree in 3 seconds compared to 12 minutes when using Push-Relabel.
@inproceedings{blasius2021efficiently, abstract = {We study the maximum-flow/minimum-cut problem on scale-free networks, i.e., graphs whose degree distribution follows a power-law. We propose a simple algorithm that capitalizes on the fact that often only a small fraction of such a network is relevant for the flow. At its core, our algorithm augments Dinitz's algorithm with a balanced bidirectional search. Our experiments on a scale-free random network model indicate sublinear run time. On scale-free real-world networks, we outperform the commonly used highest-label Push-Relabel implementation by up to two orders of magnitude. Compared to Dinitz's original algorithm, our modifications reduce the search space, e.g., by a factor of 275 on an autonomous systems graph. Beyond these good run times, our algorithm has an additional advantage compared to Push-Relabel. The latter computes a preflow, which makes the extraction of a minimum cut potentially more difficult. This is relevant, for example, for the computation of Gomory-Hu trees. On a social network with 70000 nodes, our algorithm computes the Gomory-Hu tree in 3 seconds compared to 12 minutes when using Push-Relabel.}, author = {Bläsius, Thomas and Friedrich, Tobias and Weyand, Christopher}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {christopherweyand esa thomasblaesius tobiasfriedrich year2021}, pages = {21:1-21:14}, title = {Efficiently Computing Maximum Flows in Scale-Free Networks}, year = 2021 }

Bläsius, Thomas; Fischbeck, Philipp; Gottesbüren, Lars; Hamann, Michael; Heuer, Tobias; Spinner, Jonas; Weyand, Christopher; Wilhelm, Marcus PACE Solver Description: The KaPoCE Exact Cluster Editing AlgorithmInternational Symposium on Parameterized and Exact Computation (IPEC) 2021: 27:1–27:3
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The cluster editing problem is to transform an input graph into a cluster graph by performing a minimum number of edge editing operations. A cluster graph is a graph where each connected component is a clique. An edit operation can be either adding a new edge or removing an existing edge. In this write-up we outline the core techniques used in the exact cluster editing algorithm of the KaPoCE framework (contains also a heuristic solver), submitted to the exact track of the 2021 PACE challenge.
@inproceedings{blaesius2021exact, abstract = {The cluster editing problem is to transform an input graph into a cluster graph by performing a minimum number of edge editing operations. A cluster graph is a graph where each connected component is a clique. An edit operation can be either adding a new edge or removing an existing edge. In this write-up we outline the core techniques used in the exact cluster editing algorithm of the KaPoCE framework (contains also a heuristic solver), submitted to the exact track of the 2021 PACE challenge.}, author = {Bläsius, Thomas and Fischbeck, Philipp and Gottesbüren, Lars and Hamann, Michael and Heuer, Tobias and Spinner, Jonas and Weyand, Christopher and Wilhelm, Marcus}, booktitle = {International Symposium on Parameterized and Exact Computation (IPEC)}, keywords = {christopherweyand ipec jonasspinner larsgottesbueren marcuswilhelm michaelhamann philippfischbeck thomasblaesius tobiasheuer year2021}, pages = {27:1–27:3}, title = {PACE Solver Description: The KaPoCE Exact Cluster Editing Algorithm}, year = 2021 }

Bläsius, Thomas; Fischbeck, Philipp; Gottesbüren, Lars; Hamann, Michael; Heuer, Tobias; Spinner, Jonas; Weyand, Christopher; Wilhelm, Marcus PACE Solver Description: KaPoCE: A Heuristic Cluster Editing AlgorithmInternational Symposium on Parameterized and Exact Computation (IPEC) 2021: 31:1–31:4
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The cluster editing problem is to transform an input graph into a cluster graph by performing a minimum number of edge editing operations. A cluster graph is a graph where each connected component is a clique. An edit operation can be either adding a new edge or removing an existing edge. In this write-up we outline the core techniques used in the heuristic cluster editing algorithm of the Karlsruhe and Potsdam Cluster Editing (KaPoCE) framework, submitted to the heuristic track of the 2021 PACE challenge.
@inproceedings{blaesius2021heuristic, abstract = {The cluster editing problem is to transform an input graph into a cluster graph by performing a minimum number of edge editing operations. A cluster graph is a graph where each connected component is a clique. An edit operation can be either adding a new edge or removing an existing edge. In this write-up we outline the core techniques used in the heuristic cluster editing algorithm of the Karlsruhe and Potsdam Cluster Editing (KaPoCE) framework, submitted to the heuristic track of the 2021 PACE challenge.}, author = {Bläsius, Thomas and Fischbeck, Philipp and Gottesbüren, Lars and Hamann, Michael and Heuer, Tobias and Spinner, Jonas and Weyand, Christopher and Wilhelm, Marcus}, booktitle = {International Symposium on Parameterized and Exact Computation (IPEC)}, keywords = {christopherweyand ipec jonasspinner larsgottesbueren marcuswilhelm michaelhamann philippfischbeck thomasblaesius tobiasheuer year2021}, pages = {31:1–31:4}, title = {PACE Solver Description: KaPoCE: A Heuristic Cluster Editing Algorithm}, year = 2021 }

2019 [ nach oben ]

Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Meyer, Ulrich; Penschuck, Manuel; Weyand, Christopher Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random GraphsEuropean Symposium on Algorithms (ESA) 2019: 21:2–21:14
EATCS Best Paper Award
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Hyperbolic random graphs (HRG) and geometric inhomogeneous random graphs (GIRG) are two similar generative network models that were designed to resemble complex real world networks. In particular, they have a power-law degree distribution with controllable exponent \(\beta\), and high clustering that can be controlled via the temperature \(T\). We present the first implementation of an efficient GIRG generator running in expected linear time. Besides varying temperatures, it also supports underlying geometries of higher dimensions. It is capable of generating graphs with ten million edges in under a second on commodity hardware. The algorithm can be adapted to HRGs. Our resulting implementation is the fastest sequential HRG generator, despite the fact that we support non-zero temperatures. Though non-zero temperatures are crucial for many applications, most existing generators are restricted to \(T = 0\). We also support parallelization, although this is not the focus of this paper. Moreover, we note that our generators draw from the correct probability distribution, i.e., they involve no approximation. Besides the generators themselves, we also provide an efficient algorithm to determine the non-trivial dependency between the average degree of the resulting graph and the input parameters of the GIRG model. This makes it possible to specify \(\bar{d}\) as input and obtain a graph with expected average degree \(\bar{d}\). Moreover, we investigate the differences between HRGs and GIRGs, shedding new light on the nature of the relation between the two models. Although HRGs represent, in a certain sense, a special case of the GIRG model, we find that a straight-forward inclusion does not hold in practice. However, the difference is negligible for most use cases.
@inproceedings{blaesius2019efficiently, abstract = {Hyperbolic random graphs (HRG) and geometric inhomogeneous random graphs (GIRG) are two similar generative network models that were designed to resemble complex real world networks. In particular, they have a power-law degree distribution with controllable exponent \(\beta\), and high clustering that can be controlled via the temperature \(T\). We present the first implementation of an efficient GIRG generator running in expected linear time. Besides varying temperatures, it also supports underlying geometries of higher dimensions. It is capable of generating graphs with ten million edges in under a second on commodity hardware. The algorithm can be adapted to HRGs. Our resulting implementation is the fastest sequential HRG generator, despite the fact that we support non-zero temperatures. Though non-zero temperatures are crucial for many applications, most existing generators are restricted to \(T = 0\). We also support parallelization, although this is not the focus of this paper. Moreover, we note that our generators draw from the correct probability distribution, i.e., they involve no approximation. Besides the generators themselves, we also provide an efficient algorithm to determine the non-trivial dependency between the average degree of the resulting graph and the input parameters of the GIRG model. This makes it possible to specify \(\bar{d}\) as input and obtain a graph with expected average degree \(\bar{d}\). Moreover, we investigate the differences between HRGs and GIRGs, shedding new light on the nature of the relation between the two models. Although HRGs represent, in a certain sense, a special case of the GIRG model, we find that a straight-forward inclusion does not hold in practice. However, the difference is negligible for most use cases.}, author = {Bläsius, Thomas and Friedrich, Tobias and Katzmann, Maximilian and Meyer, Ulrich and Penschuck, Manuel and Weyand, Christopher}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {christopherweyand esa hyperbolic_generation manuelpenschuck maximiliankatzmann thomasblaesius tobiasfriedrich ulrichmeyer year2019}, note = {EATCS Best Paper Award}, pages = {21:2-21:14}, title = {Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs}, year = 2019 }

2018 [ nach oben ]

Scheibel, Willy; Weyand, Christopher; Döllner, Jürgen EvoCells – A Treemap Layout Algorithm for Evolving Tree Data9th International Conference on Information Visualization Theory and Applications (IVAPP) 2018: 273–280
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We propose the rectangular treemap layout algorithm EvoCells that maps changes in tree-structured data onto an initial treemap layout. Changes in topology and node weights are mapped to insertion, removal, growth, and shrinkage of the layout rectangles. Thereby, rectangles displace their neighbors and stretch their enclosing rectangles with a run-time complexity of O(nlogn). An evaluation using layout stability metrics on the opensource ElasticSearch software system suggests EvoCells as a valid alternative for stable treemap layouting.
@inproceedings{STD2018, abstract = {We propose the rectangular treemap layout algorithm EvoCells that maps changes in tree-structured data onto an initial treemap layout. Changes in topology and node weights are mapped to insertion, removal, growth, and shrinkage of the layout rectangles. Thereby, rectangles displace their neighbors and stretch their enclosing rectangles with a run-time complexity of O(nlogn). An evaluation using layout stability metrics on the opensource ElasticSearch software system suggests EvoCells as a valid alternative for stable treemap layouting.}, author = {Scheibel, Willy and Weyand, Christopher and Döllner, Jürgen}, booktitle = {9th International Conference on Information Visualization Theory and Applications (IVAPP)}, keywords = {christopherweyand}, organization = {INSTICC}, pages = {273-280}, publisher = {SciTePress}, title = {EvoCells – A Treemap Layout Algorithm for Evolving Tree Data}, volume = 3, year = 2018 }