Lean Tree-Cut Decompositions: Obstructions and Algorithms

DOI10.4230/LIPICS.STACS.2019.32MaRDI QIDQ5090482zbMATH OpenOpenAlexFDO

Authors Archontia C. Giannopoulou, O-joung Kwon, Jean-Florent Raymond, Dimitrios M. Thilikos

Publication date 18 July 2022

Full work available at URL https://doi.org/10.4230/lipics.stacs.2019.32

zbMATH Keywords

obstructionsparameterized algorithmsimmersionstree-cut widthlean decompositions

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• A Menger-like property of tree-cut width
• Algorithmic applications of tree-cut width
• Algorithmic applications of tree-cut width
• The structure of graphs not admitting a fixed immersion

Cites work

• scientific article; zbMATH DE number 1870231 (Why is no real title available?)
• (Meta) kernelization
• A Menger-like property of tree-width: The finite case
• A \(c^k n\) 5-approximation algorithm for treewidth
• A unified treatment of linked and lean tree-decompositions
• A weak immersion relation on graphs and its applications
• Algorithmic applications of tree-cut width
• An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\)
• Branch-width and well-quasi-ordering in matroids and graphs.
• Cutwidth: obstructions and algorithmic aspects
• Finding topological subgraphs is fixed-parameter tractable
• Graph minors XXIII. Nash-Williams' immersion conjecture
• Graph minors. II. Algorithmic aspects of tree-width
• Graph minors. V. Excluding a planar graph
• Graph minors. XIII: The disjoint paths problem
• Linear kernels for edge deletion problems to immersion-closed graph classes
• Linear rank-width of distance-hereditary graphs
• Linked tree-decompositions of represented infinite matroids
• Minors in graphs of large \(\theta_r\)-girth
• Rank-width and vertex-minors
• The structure of graphs not admitting a fixed immersion
• Tournament minors
• Upper bounds on the size of obstructions and intertwines
• \(k\)-blocks: a connectivity invariant for graphs

Cited in

(6)

• Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters
• Block Stanley decompositions. II: Greedy algorithms, applications, and open problems
• \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions
• Slim tree-cut width
• Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts
• On objects dual to tree-cut decompositions

This page was built for publication: Lean Tree-Cut Decompositions: Obstructions and Algorithms

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