research
∙
08/31/2023
Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints
In this paper, we consider the problems of enumerating minimal vertex co...
share
research
∙
08/29/2023
On the hardness of inclusion-wise minimal separators enumeration
Enumeration problems are often encountered as key subroutines in the exa...
research
∙
07/18/2023
Polynomial-Delay Enumeration of Large Maximal Common Independent Sets in Two Matroids
Finding a maximum cardinality common independent set in two matroids (al...
research
∙
02/06/2023
Optimal LZ-End Parsing is Hard
LZ-End is a variant of the well-known Lempel-Ziv parsing family such tha...
research
∙
01/22/2022
A Framework to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems
Finding a single best solution is the most common objective in combinato...
research
∙
01/21/2022
An Approximation Algorithm for K-best Enumeration of Minimal Connected Edge Dominating Sets with Cardinality Constraints
K-best enumeration, which asks to output k best solutions without duplic...
research
∙
12/10/2021
Computing Diverse Shortest Paths Efficiently: A Theoretical and Experimental Study
Finding diverse solutions in combinatorial problems recently has receive...
research
∙
05/10/2021
Polynomial-Delay Enumeration of Large Maximal Matchings
Enumerating matchings is a classical problem in the field of enumeration...
research
∙
01/25/2021
Constant Amortized Time Enumeration of Eulerian trails
In this paper, we consider enumeration problems for edge-distinct and ve...
research
∙
12/09/2020
An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion
A cactus is a connected graph that does not contain K_4 - e as a minor. ...
research
∙
10/22/2020
Polynomial Delay Enumeration for Minimal Steiner Problems
Let G = (V, E) be a undirected graph and let W ⊆ V be a set of terminals...
research
∙
09/18/2020
Efficient Constant-Factor Approximate Enumeration of Minimal Subsets for Monotone Properties with Cardinality Constraints
A property Π on a finite set U is monotone if for every X ⊆ U satisfying...
research
∙
09/08/2020
Finding Diverse Trees, Paths, and More
Mathematical modeling is a standard approach to solve many real-world pr...
research
∙
06/29/2020
Efficient Enumerations for Minimal Multicuts and Multiway Cuts
Let G = (V, E) be an undirected graph and let B ⊆ V × V be a set of term...
research
∙
06/24/2019
Constant Amortized Time Enumeration of Independent Sets for Graphs with Bounded Clique Number
In this study, we address the independent set enumeration problem. Altho...
research
∙
06/24/2019
Constant Amortized Time Enumeration of Independent Sets for Graphs with Forbidden Subgraphs on Fixed Number of Vertices
In this paper, we address the independent set enumeration problem. Altho...
research
∙
03/06/2019
An Efficient Algorithm for Enumerating Chordal Bipartite Induced Subgraphs in Sparse Graphs
In this paper, we propose a characterization of chordal bipartite graphs...
research
∙
06/12/2018
Efficient Enumeration of Subgraphs and Induced Subgraphs with Bounded Girth
The girth of a graph is the length of its shortest cycle. Due to its rel...
research
∙
02/22/2018