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/04/2023
Optimally Computing Compressed Indexing Arrays Based on the Compact Directed Acyclic Word Graph
In this paper, we present the first study of the computational complexit...
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
∙
05/12/2023
Reconfiguration of Time-Respecting Arborescences
An arborescence, which is a directed analogue of a spanning tree in an u...
research
∙
05/12/2023
Minimum Consistent Subset for Trees Revisited
In a vertex-colored graph G = (V, E), a subset S ⊆ V is said to be consi...
research
∙
07/03/2022
Algorithmic Meta-Theorems for Combinatorial Reconfiguration Revisited
Given a graph and two vertex sets satisfying a certain feasibility condi...
research
∙
03/25/2022
Independent set reconfiguration on directed graphs
Directed Token Sliding asks, given a directed graph and two sets of pair...
research
∙
02/20/2022
Finding shortest non-separating and non-disconnecting paths
For a connected graph G = (V, E) and s, t ∈ V, a non-separating s-t path...
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
∙
12/10/2021
Computing Diverse Shortest Paths Efficiently: A Theoretical and Experimental Study
Finding diverse solutions in combinatorial problems recently has receive...
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/23/2021
Exploring the Gap Between Treedepth and Vertex Cover Through Vertex Integrity
For intractable problems on graphs of bounded treewidth, two graph param...
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
∙
10/05/2020
A Note on Exponential-Time Algorithms for Linearwidth
In this note, we give an algorithm that computes the linearwidth of inpu...
research
∙
09/25/2020
Finding a Maximum Minimal Separator: Graph Classes and Fixed-Parameter Tractability
We study the problem of finding a maximum cardinality minimal separator ...
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
∙
08/08/2020
Parameterized Complexity of (A,ℓ)-Path Packing
Given a graph G = (V,E), A ⊆ V, and integers k and ℓ, the (A,ℓ)-Path Pac...
research
∙
07/17/2020
Parameterized Complexity of Graph Burning
Graph Burning asks, given a graph G = (V,E) and an integer k, whether th...
research
∙
07/09/2020
Computing the Largest Bond and the Maximum Connected Cut of a Graph
The cut-set ∂(S) of a graph G=(V,E) is the set of edges that have one en...
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
∙
03/26/2020
On Structural Parameterizations of Node Kayles
Node Kayles is a well-known two-player impartial game on graphs: Given a...
research
∙
03/09/2020
Metric Learning for Ordered Labeled Trees with pq-grams
Computing the similarity between two data points plays a vital role in m...
research
∙
02/28/2020
An optimal algorithm for Bisection for bounded-treewidth graphs
The maximum/minimum bisection problems are, given an edge-weighted graph...
research
∙
10/16/2019
Algorithms and Hardness Results for the Maximum Balanced Connected Subgraph Problem
The Balanced Connected Subgraph problem (BCS) was recently introduced by...
research
∙
08/09/2019
Parameterized Algorithms for Maximum Cut with Connectivity Constraints
We study two variants of Maximum Cut, which we call Connected Maximum Cu...
research
∙
06/19/2019
Automatic Source Code Summarization with Extended Tree-LSTM
Neural machine translation models are used to automatically generate a d...
research
∙
05/25/2019
Subgraph Isomorphism on Graph Classes that Exclude a Substructure
We study Subgraph Isomorphism on graph classes defined by a fixed forbid...
research
∙
04/10/2019