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)
Recommendations
Cites work
- scientific article; zbMATH DE number 795217 (Why is no real title available?)
- A Dynamic Programming Approach to Sequencing Problems
- A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
- A polyhedral approach to planar augmentation and related problems
- A polynomial algorithm for the min-cut linear arrangement of trees
- Approximating layout problems on random geometric graphs
- Competing provers yield improved Karp-Lipton collapse results
- Computing Pathwidth Faster Than 2 n
- Computing the cutwidth of bipartite permutation graphs in linear time
- Cross-composition: a new technique for kernelization lower bounds
- Cutwidth II: Algorithms for partial w-trees of bounded degree
- Cutwidth of split graphs and threshold graphs
- Data reduction for graph coloring problems
- Dynamic Programming Treatment of the Travelling Salesman Problem
- Dynamic programming meets the principle of inclusion and exclusion
- Exact Algorithms for Treewidth and Minimum Fill-In
- Fixed-parameter algorithms for protein similarity search under mRNA structure constraints
- Graph Layout Problems Parameterized by Vertex Cover
- Infeasibility of instance compression and succinct PCPs for NP
- Kernel bounds for disjoint cycles and disjoint paths
- Kernel bounds for structural parameterizations of pathwidth
- Min Cut is NP-complete for edge weighted trees
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- New limits to classical and quantum instance compression
- On minimizing width in linear layouts
- On problems without polynomial kernels
- Optimal Linear Ordering
- Optimal labelling of unit interval graphs
- Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
- Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
- Some consequences of non-uniform conditions on uniform classes
Cited in
(8)- On cutwidth parameterized by vertex cover
- Vertex-bipartition: a unified approach for kernelization of graph linear layout problems parameterized by vertex cover
- Treewidth and pathwidth parameterized by the vertex cover number
- Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies
- Kernelization using structural parameters on sparse graph classes
- On the Parameterized Complexity of Cutting a Few Vertices from a Graph
- Treewidth and Pathwidth Parameterized by the Vertex Cover Number
- Cutwidth I: A linear time fixed parameter algorithm
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)
