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/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
∙
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
∙
08/04/2022
Core Challenge 2022: Solver and Graph Descriptions
This paper collects all descriptions of solvers and ISR instances submit...
research
∙
07/28/2022
ZDD-Based Algorithmic Framework for Solving Shortest Reconfiguration Problems
Given a graph G and two independent sets S, T of G, the independent set ...
research
∙
07/06/2022
Reforming an Envy-Free Matching
We consider the problem of reforming an envy-free matching when each age...
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/19/2022
Sorting Balls and Water: Equivalence and Computational Complexity
Various forms of sorting problems have been studied over the years. Rece...
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
∙
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
∙
07/07/2021
Reconfiguring Directed Trees in a Digraph
In this paper, we investigate the computational complexity of subgraph r...
research
∙
11/20/2020
Fixed-Parameter Algorithms for Graph Constraint Logic
Non-deterministic constraint logic (NCL) is a simple model of computatio...
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
∙
07/03/2019
Shortest Reconfiguration of Perfect Matchings via Alternating Cycles
Motivated by adjacency in perfect matching polytopes, we study the short...
research
∙
04/12/2019
The Perfect Matching Reconfiguration Problem
We study the perfect matching reconfiguration problem: Given two perfect...
research
∙
12/27/2018
Complexity of Reconfiguration Problems for Constraint Satisfaction
Constraint satisfaction problem (CSP) is a well-studied combinatorial se...
research
∙
12/13/2018
Shortest Reconfiguration of Matchings
Imagine that unlabelled tokens are placed on the edges of a graph, such ...
research
∙
04/25/2018
Incremental Optimization of Independent Sets under Reachability Constraints
We introduce a new framework for reconfiguration problems, and apply it ...
research
∙
03/16/2018
Reconfiguring spanning and induced subgraphs
Subgraph reconfiguration is a family of problems focusing on the reachab...
research
∙
02/19/2018