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

zbMATH Keywords

parameterized complexitypolynomial kernelcutwidthcomposition algorithmsvertex cover parameterization

Mathematics Subject Classification ID

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

• On cutwidth parameterized by vertex cover
• Treewidth and pathwidth parameterized by the vertex cover number
• Treewidth and Pathwidth Parameterized by the Vertex Cover Number
• Graph Layout Problems Parameterized by Vertex Cover
• Cutwidth I: A linear time fixed parameter algorithm

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)