[图书][B] Fundamentals of parameterized complexity
RG Downey, MR Fellows - 2013 - Springer
Parameterized complexity/multivariate complexity algorithmics is an exciting field of modern
algorithm design and analysis, with a broad range of theoretical and practical aspects that …
algorithm design and analysis, with a broad range of theoretical and practical aspects that …
[图书][B] Parameterized algorithms
The goal of this textbook is twofold. First, the book serves as an introduction to the field of
parameterized algorithms and complexity accessible to graduate students and advanced …
parameterized algorithms and complexity accessible to graduate students and advanced …
A survey on the computational complexity of coloring graphs with forbidden subgraphs
For a positive integer k, ak‐coloring of a graph is a mapping such that whenever. The
Coloring problem is to decide, for a given G and k, whether ak‐coloring of G exists. If k is …
Coloring problem is to decide, for a given G and k, whether ak‐coloring of G exists. If k is …
(Meta) kernelization
In a parameterized problem, every instance I comes with a positive integer k. The problem is
said to admit a polynomial kernel if, in polynomial time, one can reduce the size of the …
said to admit a polynomial kernel if, in polynomial time, one can reduce the size of the …
Structure theorem and isomorphism test for graphs with excluded topological subgraphs
We generalize the structure theorem of Robertson and Seymour for graphs excluding a fixed
graph H as a minor to graphs excluding H as a topological subgraph. We prove that for a …
graph H as a minor to graphs excluding H as a topological subgraph. We prove that for a …
[HTML][HTML] Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity
The aim of this article is to motivate and describe the parameter ecology program, which
studies how different parameters contribute to the difficulty of classical problems. We call for …
studies how different parameters contribute to the difficulty of classical problems. We call for …
Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask)
D Marx, M Pilipczuk - arXiv preprint arXiv:1307.2187, 2013 - arxiv.org
Given two graphs $ H $ and $ G $, the Subgraph Isomorphism problem asks if $ H $ is
isomorphic to a subgraph of $ G $. While NP-hard in general, algorithms exist for various …
isomorphic to a subgraph of $ G $. While NP-hard in general, algorithms exist for various …
The directed grid theorem
K Kawarabayashi, S Kreutzer - Proceedings of the forty-seventh annual …, 2015 - dl.acm.org
The grid theorem, originally proved in 1986 by Robertson and Seymour in Graph Minors V,
is one of the most central results in the study of graph minors. It has found numerous …
is one of the most central results in the study of graph minors. It has found numerous …
Minimum bisection is fixed parameter tractable
In the classic Minimum Bisection problem we are given as input a graph G and an integer k.
The task is to determine whether there is a partition of V (G) into two parts A and B such that …
The task is to determine whether there is a partition of V (G) into two parts A and B such that …
The planar directed k-vertex-disjoint paths problem is fixed-parameter tractable
Given a graph G and k pairs of vertices (s 1, t 1),...,(sk, tk), the k-Vertex-Disjoint Paths
problem asks for pair wise vertex-disjoint paths P 1,..., Pk such that Pi goes from si to ti …
problem asks for pair wise vertex-disjoint paths P 1,..., Pk such that Pi goes from si to ti …