Cutwidth: obstructions and algorithmic aspects

DOI10.1007/S00453-018-0424-7MaRDI QIDQ1725643zbMATH OpenOpenAlexFDO

Authors Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna

Publication date 14 February 2019

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00453-018-0424-7

zbMATH Keywords

fixed-parameter tractabilityobstructionscutwidthimmersions

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Cutwidth: obstructions and algorithmic aspects
• Cutwidth I: A linear time fixed parameter algorithm
• Derivation of algorithms for cutwidth and related graph layout parameters
• Algorithmic applications of tree-cut width
• Algorithmic applications of tree-cut width

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1870231 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A Menger-like property of tree-width: The finite case
• A polynomial algorithm for the min-cut linear arrangement of trees
• A weak immersion relation on graphs and its applications
• A well-quasi-order for tournaments
• An \(O(\log \mathrm{OPT})\)-approximation for covering/packing minor models of \(\theta _{r}\)
• Branch-width and well-quasi-ordering in matroids and graphs.
• Call routing and the ratcatcher
• Computing the cutwidth of bipartite permutation graphs in linear time
• Cutwidth I: A linear time fixed parameter algorithm
• Cutwidth II: Algorithms for partial w-trees of bounded degree
• Cutwidth of split graphs and threshold graphs
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Faster computation of path-width
• Graph minors XXIII. Nash-Williams' immersion conjecture
• Linear kernels for edge deletion problems to immersion-closed graph classes
• Minimal acyclic forbidden minors for the family of graphs with bounded path-width
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• The structure of graphs not admitting a fixed immersion
• Tree-width, path-width, and cutwidth
• Upper bounds on the size of obstructions and intertwines

Cited in

(16)

• A Menger-like property of tree-cut width
• \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions
• Algorithmic applications of tree-cut width
• Mathematical Foundations of Computer Science 2003
• Faster parameterized algorithms for modification problems to minor-closed classes
• Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem
• Computing Tree Decompositions
• Strong SDP based bounds on the cutwidth of a graph
• Order Reconfiguration under Width Constraints
• Cutwidth: obstructions and algorithmic aspects
• Towards Algorithmic Cut-Introduction
• Cutwidth I: A linear time fixed parameter algorithm
• Derivation of algorithms for cutwidth and related graph layout parameters
• Lean Tree-Cut Decompositions: Obstructions and Algorithms
• Lower bounds for dynamic programming on planar graphs of bounded cutwidth
• Algorithmic applications of tree-cut width

This page was built for publication: Cutwidth: obstructions and algorithmic aspects

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1725643)