scientific article
From MaRDI portal
Publication:3113681
DOI10.4230/LIPIcs.STACS.2011.165zbMath1230.68085arXiv1011.4224MaRDI QIDQ3113681
Stefan Kratsch, Bart M. P. Jansen, Hans L. Bodlaender
Publication date: 23 January 2012
Full work available at URL: https://arxiv.org/abs/1011.4224
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (46)
Disconnected matchings ⋮ Parameterized Complexity of Firefighting Revisited ⋮ On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal ⋮ Kernel Bounds for Path and Cycle Problems ⋮ On the Hardness of Losing Width ⋮ On Cutwidth Parameterized by Vertex Cover ⋮ Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds ⋮ New Limits to Classical and Quantum Instance Compression ⋮ Kernelization – Preprocessing with a Guarantee ⋮ Satisfying more than half of a system of linear equations over GF(2): a multivariate approach ⋮ The Flood-It game parameterized by the vertex cover number ⋮ Two edge modification problems without polynomial kernels ⋮ Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter ⋮ Preprocessing subgraph and minor problems: when does a small vertex cover help? ⋮ Kernel bounds for path and cycle problems ⋮ Data reduction for graph coloring problems ⋮ Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique ⋮ Structural parameterizations for equitable coloring: complexity, FPT algorithms, and kernelization ⋮ Weighted connected matchings ⋮ Fixing improper colorings of graphs ⋮ FPT and kernelization algorithms for the induced tree problem ⋮ On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems ⋮ Kernel bounds for disjoint cycles and disjoint paths ⋮ On Structural Parameterizations of Graph Motif and Chromatic Number ⋮ Perfectly matched sets in graphs: parameterized and exact computation ⋮ On the hardness of losing width ⋮ Parameterized complexity of Eulerian deletion problems ⋮ Parameterized algorithms for load coloring problem ⋮ Confronting intractability via parameters ⋮ On cutwidth parameterized by vertex cover ⋮ Parameterized complexity of firefighting ⋮ Restricted and swap common superstring: a multivariate algorithmic perspective ⋮ Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization ⋮ Unnamed Item ⋮ Kernelization hardness of connectivity problems in \(d\)-degenerate graphs ⋮ Parameterized complexity of a coupled-task scheduling problem ⋮ Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization ⋮ Data Reduction for Graph Coloring Problems ⋮ A multivariate analysis of the strict terminal connection problem ⋮ FPT is characterized by useful obstruction sets ⋮ Parameterized Complexity of Eulerian Deletion Problems ⋮ Kernelization lower bound for permutation pattern matching ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Editing to a graph of given degrees
This page was built for publication:
