research
∙
07/15/2023
Minimum Separator Reconfiguration
We study the problem of reconfiguring one minimum s-t-separator A into a...
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/06/2022
Reforming an Envy-Free Matching
We consider the problem of reforming an envy-free matching when each age...
research
∙
05/16/2022
Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds
We consider the unlabeled motion-planning problem of m unit-disc robots ...
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
∙
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/23/2019
Variants of the Segment Number of a Graph
The segment number of a planar graph is the smallest number of line segm...
research
∙
08/18/2019
Graphs with large total angular resolution
The total angular resolution of a straight-line drawing is the minimum a...
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/25/2019
Subgraph Isomorphism on Graph Classes that Exclude a Substructure
We study Subgraph Isomorphism on graph classes defined by a fixed forbid...
research
∙
08/30/2018
Orthogonal and Smooth Orthogonal Layouts of 1-Planar Graphs with Low Edge Complexity
While orthogonal drawings have a long history, smooth orthogonal drawing...
research
∙
12/15/2017
Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain
We study the computation of the diameter and radius under the rectilinea...
research
∙
09/08/2017