Cutwidth: obstructions and algorithmic aspects

DOI10.1007/S00453-018-0424-7zbMATH Open1414.68035OpenAlexW2997810375MaRDI QIDQ1725643FDOQ1725643

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)

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

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

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)

Cites Work

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

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
• Cutwidth I: A linear time fixed parameter algorithm
• Towards Algorithmic Cut-Introduction
• 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)