research
∙
05/12/2023
Reconfiguration of Time-Respecting Arborescences
An arborescence, which is a directed analogue of a spanning tree in an u...
share
research
∙
05/07/2023
EFX Allocations for Indivisible Chores: Matching-Based Approach
One of the most important topics in discrete fair division is whether an...
research
∙
05/03/2023
Algorithmic Theory of Qubit Routing
The qubit routing problem, also known as the swap minimization problem, ...
research
∙
04/28/2023
Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra
We prove that the computation of a combinatorial shortest path between t...
research
∙
04/26/2023
An Approximation Algorithm for Two-Edge-Connected Subgraph Problem via Triangle-free Two-Edge-Cover
The 2-Edge-Connected Spanning Subgraph problem (2-ECSS) is one of the mo...
research
∙
04/26/2023
Reconfiguration of the Union of Arborescences
An arborescence in a digraph is an acyclic arc subset in which every ver...
research
∙
10/31/2022
Reconfiguration of colorings in triangulations of the sphere
In 1973, Fisk proved that any 4-coloring of a 3-colorable triangulation ...
research
∙
10/21/2022
Rerouting Planar Curves and Disjoint Paths
In this paper, we consider a transformation of k disjoint paths in a gra...
research
∙
09/21/2022
On Reachable Assignments under Dichotomous Preferences
We consider the problem of determining whether a target item assignment ...
research
∙
09/02/2022
Optimal General Factor Problem and Jump System Intersection
In the optimal general factor problem, given a graph G=(V, E) and a set ...
research
∙
07/06/2022
Reforming an Envy-Free Matching
We consider the problem of reforming an envy-free matching when each age...
research
∙
04/30/2022
Proportional Allocation of Indivisible Goods up to the Least Valued Good on Average
We study the problem of fairly allocating a set of indivisible goods to ...
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/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
∙
01/05/2022
An Additive Approximation Scheme for the Nash Social Welfare Maximization with Identical Additive Valuations
We study the problem of efficiently and fairly allocating a set of indiv...
research
∙
10/22/2021
Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams
We initiate the study of k-edge-connected orientations of undirected gra...
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
∙
11/20/2020
Fixed-Parameter Algorithms for Graph Constraint Logic
Non-deterministic constraint logic (NCL) is a simple model of computatio...
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
∙
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
Market Pricing for Matroid Rank Valuations
In this paper, we study the problem of maximizing social welfare in comb...
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/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/08/2020
Envy-free Relaxations for Goods, Chores, and Mixed Items
In fair division problems, we are given a set S of m items and a set N o...
research
∙
11/15/2019
Weighted Triangle-free 2-matching Problem with Edge-disjoint Forbidden Triangles
The weighted T-free 2-matching problem is the following problem: given a...
research
∙
09/20/2019
Linear-Time Recognition of Double-Threshold Graphs
A graph G = (V,E) is a double-threshold graph if there exist a vertex-we...
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
∙
07/03/2019
Shortest Reconfiguration of Perfect Matchings via Alternating Cycles
Motivated by adjacency in perfect matching polytopes, we study the short...
research
∙
05/31/2019
A Weighted Linear Matroid Parity Algorithm
The matroid parity (or matroid matching) problem, introduced as a common...
research
∙
05/29/2019
Improved Analysis of Highest-Degree Branching for Feedback Vertex Set
Recent empirical evaluations of exact algorithms for Feedback Vertex Set...
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/12/2019
The Perfect Matching Reconfiguration Problem
We study the perfect matching reconfiguration problem: Given two perfect...
research
∙
04/10/2019
An FPT Algorithm for Max-Cut Parameterized by Crossing Number
The Max-Cut problem is known to be NP-hard on general graphs, while it c...
research
∙
03/04/2019
An FPT Algorithm for Minimum Additive Spanner Problem
For a positive integer t and a graph G, an additive t-spanner of G is a ...
research
∙
11/22/2018
Tight Approximation for Unconstrained XOS Maximization
A set function is called XOS if it can be represented by the maximum of ...
research
∙
06/30/2018