research
∙
07/06/2023
Shortest Beer Path Queries based on Graph Decomposition
Given a directed edge-weighted graph G=(V, E) with beer vertices B⊆ V, a...
share
research
∙
03/02/2023
Solving Distance-constrained Labeling Problems for Small Diameter Graphs via TSP
In this paper, we give a simple polynomial-time reduction of L(p)-Labeli...
research
∙
02/14/2023
Grouped Domination Parameterized by Vertex Cover, Twin Cover, and Beyond
A dominating set S of graph G is called an r-grouped dominating set if S...
research
∙
11/10/2022
Winner Determination Algorithms for Graph Games with Matching Structures
Cram, Domineering, and Arc Kayles are well-studied combinatorial games. ...
research
∙
07/20/2022
Computing Densest k-Subgraph with Structural Parameters
Densest k-Subgraph is the problem to find a vertex subset S of size k su...
research
∙
02/14/2022
Hedonic Games and Treewidth Revisited
We revisit the complexity of the well-studied notion of Additively Separ...
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
∙
07/07/2021
Capacitated Network Design Games on a Generalized Fair Allocation Model
The cost-sharing connection game is a variant of routing games on a netw...
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
∙
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/22/2020
Computing L(p,1)-Labeling with Combined Parameters
Given a graph, an L(p,1)-labeling of the graph is an assignment f from t...
research
∙
09/21/2020
(In)approximability of Maximum Minimal FVS
We study the approximability of the NP-complete Maximum Minimal Feedback...
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/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
∙
02/28/2020
An optimal algorithm for Bisection for bounded-treewidth graphs
The maximum/minimum bisection problems are, given an edge-weighted graph...
research
∙
02/25/2020
Hedonic Seat Arrangement Problems
In this paper, we study a variant of hedonic games, called Seat Arrangem...
research
∙
08/30/2019
Computational Complexity of Hedonic Games on Sparse Graphs
The additively separable hedonic game (ASHG) is a model of coalition for...
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
∙
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
∙
05/01/2019
Independent Set Reconfiguration Parameterized by Modular-Width
Independent Set Reconfiguration is one of the most well-studied problems...
research
∙
02/13/2019
New Results on Directed Edge Dominating Set
We study a family of generalizations of Edge Dominating Set on directed ...
research
∙
01/27/2019
Parameterized Complexity of Safe Set
In this paper we study the problem of finding a small safe set S in a gr...
research
∙
09/10/2018
Optimal Partition of a Tree with Social Distance
We study the problem to find a partition of graph G with maximum social ...
research
∙
07/30/2018
Parameterized Orientable Deletion
A graph is d-orientable if its edges can be oriented so that the maximum...
research
∙
03/16/2018