On cutwidth parameterized by vertex cover

DOI10.1007/s00453-012-9707-6zbMath1303.05185OpenAlexW2180300668WikidataQ59397976 ScholiaQ59397976MaRDI QIDQ476444

Marek Cygan, Saket Saurabh, Michał Pilipczuk, Daniel Lokshtanov, Marcin Pilipczuk

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

zbMATH Keywords

cutwidthparameterized complexitypolynomial kernelcomposition algorithmsvertex cover parameterization

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) 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) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies ⋮ Kernelization using structural parameters on sparse graph classes ⋮ Treewidth and pathwidth parameterized by the vertex cover number ⋮ Algorithms parameterized by vertex cover and modular width, through potential maximal cliques

Cites Work

• Unnamed Item
• Unnamed Item
• Infeasibility of instance compression and succinct PCPs for NP
• Kernel bounds for disjoint cycles and disjoint paths
• On minimizing width in linear layouts
• Some consequences of non-uniform conditions on uniform classes
• Fixed-parameter algorithms for protein similarity search under mRNA structure constraints
• On problems without polynomial kernels
• Min Cut is NP-complete for edge weighted trees
• Dynamic programming meets the principle of inclusion and exclusion
• Competing provers yield improved Karp-Lipton collapse results
• Optimal labelling of unit interval graphs
• Approximating Layout Problems on Random Geometric Graphs
• Kernel Bounds for Structural Parameterizations of Pathwidth
• 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
• Cutwidth of Split Graphs and Threshold Graphs
• Dynamic Programming Treatment of the Travelling Salesman Problem
• A Dynamic Programming Approach to Sequencing Problems
• New Limits to Classical and Quantum Instance Compression
• 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 II: Algorithms for partial w-trees of bounded degree
• A polyhedral approach to planar augmentation and related problems

This page was built for publication: On cutwidth parameterized by vertex cover