![Loading...](https://link.springer.com/static/c4a417b97a76cc2980e3c25e2271af3129e08bbe/images/pdf-preview/spacer.gif)
-
Chapter and Conference Paper
Multidimensional Stable Roommates with Master List
Since the early days of research in algorithms and complexity, the computation of stable matchings is a core topic. While in the classic setting the goal is to match up two agents (either from different “gende...
-
Chapter and Conference Paper
Graph Isomorphism Restricted by Lists
The complexity of graph isomorphism (GraphIso) is a famous problem in computer science. For graphs G and H, it asks whether they are the same up to a relabeling of vertices. In 1981, Lubiw proved that list restri...
-
Chapter and Conference Paper
Integer Programming and Incidence Treedepth
Recently a strong connection has been shown between the tractability of integer programming (IP) with bounded coefficients on the one side and the structure of its constraint matrix on the other side. To that ...
-
Chapter and Conference Paper
Kernelization of Graph Hamiltonicity: Proper H-Graphs
We obtain new polynomial kernels and compression algorithms for Pat...
-
Chapter and Conference Paper
Partitioning Graphs into Induced Subgraphs
We study the Partition into \(H\) problem from the parametrized complexity point of view. In the Partition ...
-
Chapter and Conference Paper
Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity
This paper settles the computational complexity of model checking of several extensions of the monadic second order (MSO) logic on two classes of graphs: graphs of bounded treewidth and graphs of bounded neighbor...
-
Chapter and Conference Paper
Computational Complexity of Distance Edge Labeling
The problem of Distance Edge Labeling is a variant of Distance Vertex Labeling (also known as \(\mathrm{L}_{2,1}\) la...
-
Chapter and Conference Paper
Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems
We study computational complexity of the class of distance-constrained graph labeling problems from the fixed parameter tractability point of view. The parameters studied are neighborhood diversity and clique ...
-
Chapter and Conference Paper
Parametrized Complexity of Length-Bounded Cuts and Multi-cuts
We show that the minimal length-bounded \(L\) -cut can be computed in linear time with respect to