research
∙
07/25/2023
A Dual-mode Local Search Algorithm for Solving the Minimum Dominating Set Problem
Given a graph, the minimum dominating set (MinDS) problem is to identify...
share
research
∙
06/30/2023
Solving Edge Clique Cover Exactly via Synergistic Data Reduction
The edge clique cover (ECC) problem – where the goal is to find a minimu...
research
∙
02/01/2023
Improved Exact and Heuristic Algorithms for Maximum Weight Clique
We propose improved exact and heuristic algorithms for solving the maxim...
research
∙
08/29/2022
Finding Near-Optimal Weight Independent Sets at Scale
Computing maximum weight independent sets in graphs is an important NP-h...
research
∙
12/23/2020
Recent Advances in Practical Data Reduction
Over the last two decades, significant advances have been made in the de...
research
∙
08/12/2020
Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations
Given a vertex-weighted graph, the maximum weight independent set proble...
research
∙
04/23/2020
Engineering Data Reduction for Nested Dissection
Many applications rely on time-intensive matrix operations, such as fact...
research
∙
02/17/2020
Finding All Global Minimum Cuts In Practice
We present a practically efficient algorithm that finds all global minim...
research
∙
08/23/2019
Simultaneous Representation of Proper and Unit Interval Graphs
In a confluence of combinatorics and geometry, simultaneous representati...
research
∙
08/19/2019
WeGotYouCovered: The Winning Solver from the PACE 2019 Implementation Challenge, Vertex Cover Track
We present the winning solver of the PACE 2019 Implementation Challenge,...
research
∙
06/03/2019
On Romeo and Juliet Problems: Minimizing Distance-to-Sight
We introduce a variant of the watchman route problem, which we call the ...
research
∙
05/26/2019
Engineering Kernelization for Maximum Cut
Kernelization is a general theoretical framework for preprocessing insta...
research
∙
10/25/2018
Exactly Solving the Maximum Weight Independent Set Problem on Large Real-World Graphs
One powerful technique to solve NP-hard optimization problems in practic...
research
∙
08/20/2018
Scalable Edge Partitioning
Edge-centric distributed computations have appeared as a recent techniqu...
research
∙
02/19/2018
Convexity-Increasing Morphs of Planar Graphs
We study the problem of convexifying drawings of planar graphs. Given an...
research
∙
12/30/2017
Efficiently Enumerating all Maximal Cliques with Bit-Parallelism
The maximal clique enumeration (MCE) problem has numerous applications i...
research
∙
10/20/2017
Communication-free Massively Distributed Graph Generation
Analyzing massive complex networks yields promising insights about our e...
research
∙
02/06/2017
Distributed Evolutionary k-way Node Separators
Computing high quality node separators in large graphs is necessary for ...
research
∙
09/02/2015
Finding Near-Optimal Independent Sets at Scale
The independent set problem is NP-hard and particularly difficult to sol...
research
∙
12/04/2008