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
∙
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...
research
∙
05/18/2023
On the Computational Complexity of Generalized Common Shape Puzzles
In this study, we investigate the computational complexity of some varia...
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
∙
10/06/2022
Sequentially Swapping Tokens: Further on Graph Classes
We study the following variant of the 15 puzzle. Given a graph and two t...
research
∙
11/04/2021
Reallocation Problems with Minimum Completion Time
Reallocation scheduling is one of the most fundamental problems in vario...
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
∙
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
∙
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/16/2020
Fair Ride Allocation on a Line
With the advent of the ride-sharing platform, the carpooling has become ...
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
∙
05/01/2019
Independent Set Reconfiguration Parameterized by Modular-Width
Independent Set Reconfiguration is one of the most well-studied problems...
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
∙
12/26/2017
