Publications (39)
On Minimizing Crossings in Storyline Visualizations
Irina Kostitsyna, Martin Nöllenburg, Valentin Polishchuk +2
In a storyline visualization, we visualize a collection of interacting characters (e.g., in a movie, play, etc.) by -monotone curves that converge for each interaction, and dive…
Priority Range Trees
Michael T. Goodrich, Darren Strash
We describe a data structure, called a priority range tree, which accommodates fast orthogonal range reporting queries on prioritized points. Let be a set of points in the…
A Dual-mode Local Search Algorithm for Solving the Minimum Dominating Set Problem
Enqiang Zhu, Yu Zhang, Shengzhi Wang +2
Given a graph, the minimum dominating set (MinDS) problem is to identify a smallest set of vertices such that every vertex not in is adjacent to at least one vertex in .…
Simultaneous Representation of Proper and Unit Interval Graphs
Ignaz Rutter, Darren Strash, Peter Stumpf +1
In a confluence of combinatorics and geometry, simultaneous representations provide a way to realize combinatorial objects that share common structure. A standard case in the study…
Distributed Evolutionary k-way Node Separators
Peter Sanders, Christian Schulz, Darren Strash +1
Computing high quality node separators in large graphs is necessary for a variety of applications, ranging from divide-and-conquer algorithms to VLSI design. In this work, we prese…
Engineering Kernelization for Maximum Cut
Damir Ferizovic, Demian Hespe, Sebastian Lamm +3
Kernelization is a general theoretical framework for preprocessing instances of NP-hard problems into (generally smaller) instances with bounded size, via the repeated application…
Dynamic Planar Point Location with Sub-Logarithmic Local Updates
Maarten Löffler, Joe Simons, Darren Strash
We study planar point location in a collection of disjoint fat regions, and investigate the complexity of \emph {local updates}: replacing any region by a different region that is…
Improved Exact and Heuristic Algorithms for Maximum Weight Clique
Roman Erhardt, Kathrin Hanauer, Nils Kriege +2
We propose improved exact and heuristic algorithms for solving the maximum weight clique problem, a well-known problem in graph theory with many applications. Our algorithms interl…
Finding All Global Minimum Cuts In Practice
Monika Henzinger, Alexander Noe, Christian Schulz +1
We present a practically efficient algorithm that finds all global minimum cuts in huge undirected graphs. Our algorithm uses a multitude of kernelization rules to reduce the graph…
Finding Near-Optimal Independent Sets at Scale
Sebastian Lamm, Peter Sanders, Christian Schulz +2
The independent set problem is NP-hard and particularly difficult to solve in large sparse graphs. In this work, we develop an advanced evolutionary algorithm, which incorporates k…
Recent Advances in Practical Data Reduction
Faisal Abu-Khzam, Sebastian Lamm, Matthias Mnich +3
Over the last two decades, significant advances have been made in the design and analysis of fixed-parameter algorithms for a wide variety of graph-theoretic problems. This has res…
Temporal Map Labeling: A New Unified Framework with Experiments
Lukas Barth, Benjamin Niedermann, Martin Nöllenburg +1
The increased availability of interactive maps on the Internet and on personal mobile devices has created new challenges in computational cartography and, in particular, for label…
Listing All Maximal Cliques in Large Sparse Real-World Graphs
David Eppstein, Darren Strash
We implement a new algorithm for listing all maximal cliques in sparse graphs due to Eppstein, Löffler, and Strash (ISAAC 2010) and analyze its performance on a large corpus of re…
On the Complexity of Barrier Resilience for Fat Regions
Matias Korman, Maarten Löffler, Rodrigo I. Silveira +1
In the \emph {barrier resilience} problem (introduced by Kumar {\em et al.}, Wireless Networks 2007), we are given a collection of regions of the plane, acting as obstacles, and we…
On the Power of Simple Reductions for the Maximum Independent Set Problem
Darren Strash
Reductions---rules that reduce input size while maintaining the ability to compute an optimal solution---are critical for developing efficient maximum independent set algorithms in…
Exactly Solving the Maximum Weight Independent Set Problem on Large Real-World Graphs
Sebastian Lamm, Christian Schulz, Darren Strash +2
One powerful technique to solve NP-hard optimization problems in practice is branch-and-reduce search---which is branch-and-bound that intermixes branching with reductions to decre…
Practical Minimum Cut Algorithms
Monika Henzinger, Alexander Noe, Christian Schulz +1
The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weight sum of the cut edges. Here, we introduc…
Scalable Kernelization for Maximum Independent Sets
Demian Hespe, Christian Schulz, Darren Strash
The most efficient algorithms for finding maximum independent sets in both theory and practice use reduction rules to obtain a much smaller problem instance called a kernel. The ke…
Open Problems in (Hyper)Graph Decomposition
Deepak Ajwani, Rob H. Bisseling, Katrin Casel +26
Large networks are useful in a wide range of applications. Sometimes problem instances are composed of billions of entities. Decomposing and analyzing these structures helps us gai…
WeGotYouCovered: The Winning Solver from the PACE 2019 Implementation Challenge, Vertex Cover Track
Demian Hespe, Sebastian Lamm, Christian Schulz +1
We present the winning solver of the PACE 2019 Implementation Challenge, Vertex Cover Track. The minimum vertex cover problem is one of a handful of problems for which kernelizatio…
Communication-free Massively Distributed Graph Generation
Daniel Funke, Sebastian Lamm, Ulrich Meyer +5
Analyzing massive complex networks yields promising insights about our everyday lives. Building scalable algorithms to do so is a challenging task that requires a careful analysis…
Reconstructing Generalized Staircase Polygons with Uniform Step Length
Nodari Sitchinava, Darren Strash
Visibility graph reconstruction, which asks us to construct a polygon that has a given visibility graph, is a fundamental problem with unknown complexity (although visibility graph…
Solving Edge Clique Cover Exactly via Synergistic Data Reduction
Anthony Hevia, Benjamin Kallus, Summer McClintic +3
The edge clique cover (ECC) problem -- where the goal is to find a minimum cardinality set of cliques that cover all the edges of a graph -- is a classic NP-hard problem that has r…
Category-Based Routing in Social Networks: Membership Dimension and the Small-World Phenomenon (Short)
David Eppstein, Michael T. Goodrich, Maarten Löffler +2
A classic experiment by Milgram shows that individuals can route messages along short paths in social networks, given only simple categorical information about recipients (such as…
Extended h-Index Parameterized Data Structures for Computing Dynamic Subgraph Statistics
David Eppstein, Michael T. Goodrich, Darren Strash +1
We present techniques for maintaining subgraph frequencies in a dynamic graph, using data structures that are parameterized in terms of h, the h-index of the graph. Our methods ext…
Succinct Greedy Geometric Routing in the Euclidean Plane
Michael T. Goodrich, Darren Strash
In greedy geometric routing, messages are passed in a network embedded in a metric space according to the greedy strategy of always forwarding messages to nodes that are closer to…
Category-Based Routing in Social Networks: Membership Dimension and the Small-World Phenomenon (Full)
David Eppstein, Michael T. Goodrich, Maarten Löffler +2
A classic experiment by Milgram shows that individuals can route messages along short paths in social networks, given only simple categorical information about recipients (such as…
Listing All Maximal Cliques in Sparse Graphs in Near-optimal Time
David Eppstein, Maarten Löffler, Darren Strash
The degeneracy of an -vertex graph is the smallest number such that every subgraph of contains a vertex of degree at most . We show that there exists a nearly-opt…
Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations
Alexander Gellner, Sebastian Lamm, Christian Schulz +2
Given a vertex-weighted graph, the maximum weight independent set problem asks for a pair-wise non-adjacent set of vertices such that the sum of their weights is maximum. The branc…
Scalable Edge Partitioning
Sebastian Schlag, Christian Schulz, Daniel Seemaier +1
Edge-centric distributed computations have appeared as a recent technique to improve the shortcomings of think-like-a-vertex algorithms on large scale-free networks. In order to in…
On Romeo and Juliet Problems: Minimizing Distance-to-Sight
Hee-Kap Ahn, Eunjin Oh, Lena Schlipf +2
We introduce a variant of the watchman route problem, which we call the quickest pair-visibility problem. Given two persons standing at points and in a simple polygon w…
Data Reductions for the Strong Maximum Independent Set Problem in Hypergraphs
Ernestine GroÃmann, Christian Schulz, Darren Strash +1
This work addresses the well-known Maximum Independent Set problem in the context of hypergraphs. While this problem has been extensively studied on graphs, we focus on its strong…
Finding Near-Optimal Weight Independent Sets at Scale
Ernestine GroÃmann, Sebastian Lamm, Christian Schulz +1
Computing maximum weight independent sets in graphs is an important NP-hard optimization problem. The problem is particularly difficult to solve in large graphs for which data redu…
Convexity-Increasing Morphs of Planar Graphs
Linda Kleist, Boris Klemz, Anna Lubiw +3
We study the problem of convexifying drawings of planar graphs. Given any planar straight-line drawing of an internally 3-connected graph, we show how to morph the drawing to one w…
Shared Memory Parallel Subgraph Enumeration
Raphael Kimmig, Henning Meyerhenke, Darren Strash
The subgraph enumeration problem asks us to find all subgraphs of a target graph that are isomorphic to a given pattern graph. Determining whether even one such isomorphic subgraph…
Accelerating Local Search for the Maximum Independent Set Problem
Jakob Dahlum, Sebastian Lamm, Peter Sanders +3
Computing high-quality independent sets quickly is an important problem in combinatorial optimization. Several recent algorithms have shown that kernelization techniques can be use…
Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Edge Crossings
David Eppstein, Michael T. Goodrich, Darren Strash
We provide linear-time algorithms for geometric graphs with sublinearly many crossings. That is, we provide algorithms running in O(n) time on connected geometric graphs having n v…
Engineering Data Reduction for Nested Dissection
Lara Ost, Christian Schulz, Darren Strash
Many applications rely on time-intensive matrix operations, such as factorization, which can be sped up significantly for large sparse matrices by interpreting the matrix as a spar…
Efficiently Enumerating all Maximal Cliques with Bit-Parallelism
Pablo San Segundo, Jorge Artieda, Darren Strash
The maximal clique enumeration (MCE) problem has numerous applications in biology, chemistry, sociology, and graph modeling. Though this problem is well studied, most current resea…