On Cutwidth Parameterized by Vertex Cover
From MaRDI portal
Publication:2891354
DOI10.1007/978-3-642-28050-4_20zbMath1352.68099OpenAlexW2140699162MaRDI QIDQ2891354
Daniel Lokshtanov, Marek Cygan, Saket Saurabh, Michał Pilipczuk, Marcin Pilipczuk
Publication date: 15 June 2012
Published in: Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: http://wrap.warwick.ac.uk/66061/1/WRAP_art%253A10.1007%252Fs00453-012-9707-6.pdf
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items
Preprocessing subgraph and minor problems: when does a small vertex cover help? ⋮ Maximum common induced subgraph parameterized by vertex cover ⋮ Computing tree-depth faster than \(2^n\)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On minimizing width in linear layouts
- Fixed-parameter algorithms for protein similarity search under mRNA structure constraints
- Min Cut is NP-complete for edge weighted trees
- Dynamic programming meets the principle of inclusion and exclusion
- Optimal labelling of unit interval graphs
- Approximating Layout Problems on Random Geometric Graphs
- Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
- Computing the Cutwidth of Bipartite Permutation Graphs in Linear Time
- Data Reduction for Graph Coloring Problems
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Dynamic Programming Treatment of the Travelling Salesman Problem
- A Dynamic Programming Approach to Sequencing Problems
- Graph Layout Problems Parameterized by Vertex Cover
- Exact Algorithms for Treewidth and Minimum Fill-In
- Computing Pathwidth Faster Than 2 n
- Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
- 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
- Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs
- Cutwidth II: Algorithms for partial w-trees of bounded degree
