On cutwidth parameterized by vertex cover
DOI10.1007/S00453-012-9707-6zbMATH Open1303.05185OpenAlexW2180300668WikidataQ59397976 ScholiaQ59397976MaRDI QIDQ476444FDOQ476444
Authors: Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh 
Publication date: 2 December 2014
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9707-6
Recommendations
parameterized complexitypolynomial kernelcutwidthcomposition algorithmsvertex cover parameterization
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- A Dynamic Programming Approach to Sequencing Problems
- On problems without polynomial kernels
- Min Cut is NP-complete for edge weighted trees
- Infeasibility of instance compression and succinct PCPs for NP
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Dynamic Programming Treatment of the Travelling Salesman Problem
- New Limits to Classical and Quantum Instance Compression
- Exact Algorithms for Treewidth and Minimum Fill-In
- Computing Pathwidth Faster Than 2 n
- Kernel bounds for disjoint cycles and disjoint paths
- Some consequences of non-uniform conditions on uniform classes
- Graph Layout Problems Parameterized by Vertex Cover
- Competing provers yield improved Karp-Lipton collapse results
- Data reduction for graph coloring problems
- Cross-composition: a new technique for kernelization lower bounds
- Optimal labelling of unit interval graphs
- A polynomial algorithm for the min-cut linear arrangement of trees
- A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
- Optimal Linear Ordering
- On minimizing width in linear layouts
- Approximating layout problems on random geometric graphs
- Kernel bounds for structural parameterizations of pathwidth
- Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
- Title not available (Why is that?)
- Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
- Cutwidth II: Algorithms for partial w-trees of bounded degree
- Fixed-parameter algorithms for protein similarity search under mRNA structure constraints
- Dynamic programming meets the principle of inclusion and exclusion
- Computing the cutwidth of bipartite permutation graphs in linear time
- Cutwidth of split graphs and threshold graphs
- A polyhedral approach to planar augmentation and related problems
Cited In (8)
- On the Parameterized Complexity of Cutting a Few Vertices from a Graph
- Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies
- Treewidth and Pathwidth Parameterized by the Vertex Cover Number
- Kernelization using structural parameters on sparse graph classes
- Cutwidth I: A linear time fixed parameter algorithm
- Treewidth and pathwidth parameterized by the vertex cover number
- On cutwidth parameterized by vertex cover
- Algorithms parameterized by vertex cover and modular width, through potential maximal cliques
This page was built for publication: On cutwidth parameterized by vertex cover
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q476444)
