On Cutwidth Parameterized by Vertex Cover

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

Mathematics Subject Classification ID

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