research
∙
08/29/2023
On the hardness of inclusion-wise minimal separators enumeration
Enumeration problems are often encountered as key subroutines in the exa...
share
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/01/2023
Hardness of braided quantum circuit optimization in the surface code
Large-scale quantum information processing requires the use of quantum e...
research
∙
03/25/2022
Independent set reconfiguration on directed graphs
Directed Token Sliding asks, given a directed graph and two sets of pair...
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
∙
01/12/2022
Reconfiguration of Spanning Trees with Degree Constraint or Diameter Constraint
We investigate the complexity of finding a transformation from a given s...
research
∙
11/26/2021
Reconfiguration of Regular Induced Subgraphs
We study the problem of checking the existence of a step-by-step transfo...
research
∙
07/07/2021
Reconfiguring Directed Trees in a Digraph
In this paper, we investigate the computational complexity of subgraph r...
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
∙
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
∙
06/25/2020
Reconfiguration of Spanning Trees with Many or Few Leaves
Let G be a graph and T_1,T_2 be two spanning trees of G. We say that T_1...
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
∙
04/12/2019
The Perfect Matching Reconfiguration Problem
We study the perfect matching reconfiguration problem: Given two perfect...
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
∙
03/10/2018
Efficient Enumeration of Bipartite Subgraphs in Graphs
Subgraph enumeration problems ask to output all subgraphs of an input gr...
research
∙
02/22/2018