Cutwidth: obstructions and algorithmic aspects
From MaRDI portal
Publication:1725643
DOI10.1007/S00453-018-0424-7zbMath1414.68035OpenAlexW2997810375MaRDI QIDQ1725643
Jean-Florent Raymond, Archontia C. Giannopoulou, Michał Pilipczuk, Marcin Wrochna, Dimitrios M. Thilikos
Publication date: 14 February 2019
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-018-0424-7
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (8)
Computing Tree Decompositions ⋮ \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions ⋮ Strong SDP based bounds on the cutwidth of a graph ⋮ Order Reconfiguration under Width Constraints ⋮ Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth ⋮ A Menger-like property of tree-cut width ⋮ Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem ⋮ Lean Tree-Cut Decompositions: Obstructions and Algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- The structure of graphs not admitting a fixed immersion
- A well-quasi-order for tournaments
- Graph minors XXIII. Nash-Williams' immersion conjecture
- A Menger-like property of tree-width: The finite case
- Upper bounds on the size of obstructions and intertwines
- Minimal acyclic forbidden minors for the family of graphs with bounded path-width
- Call routing and the ratcatcher
- Tree-width, path-width, and cutwidth
- Branch-width and well-quasi-ordering in matroids and graphs.
- An $$O(\log \mathrm{OPT})$$ O ( log OPT ) -Approximation for Covering/Packing Minor Models of $$\theta _{r}$$ θ r
- Faster Computation of Path-Width
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Cutwidth of Split Graphs and Threshold Graphs
- A polynomial algorithm for the min-cut linear arrangement of trees
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- Computing the Cutwidth of Bipartite Permutation Graphs in Linear Time
- Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
- Cutwidth I: A linear time fixed parameter algorithm
- Cutwidth II: Algorithms for partial w-trees of bounded degree
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A weak immersion relation on graphs and its applications
This page was built for publication: Cutwidth: obstructions and algorithmic aspects
