Large-treewidth graph decompositions and applications
From MaRDI portal
Publication:5495799
DOI10.1145/2488608.2488645zbMath1293.05040arXiv1304.1577OpenAlexW2033480692MaRDI QIDQ5495799
Julia Chuzhoy, Chandra Chekuri
Publication date: 7 August 2014
Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1304.1577
Trees (05C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph designs and isomorphic decomposition (05C51)
Related Items (19)
An edge variant of the Erdős-Pósa property ⋮ Packing and Covering Immersion Models of Planar Subcubic Graphs ⋮ Constant Congestion Brambles in Directed Graphs ⋮ A tight Erdős-Pósa function for long cycles ⋮ Frames, $A$-Paths, and the Erdös--Pósa Property ⋮ Minors in graphs of large \(\theta_r\)-girth ⋮ Packing and covering immersion-expansions of planar sub-cubic graphs ⋮ Recent techniques and results on the Erdős-Pósa property ⋮ Erdös-Pósa Property of Obstructions to Interval Graphs ⋮ Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs ⋮ Polynomial expansion and sublinear separators ⋮ Erdős–Pósa property of obstructions to interval graphs ⋮ The all-or-nothing flow problem in directed graphs with symmetric demand pairs ⋮ A Tight Erdös--Pósa Function for Wheel Minors ⋮ Explicit linear kernels for packing problems ⋮ An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\) ⋮ Unnamed Item ⋮ Routing in Undirected Graphs with Constant Congestion ⋮ Packing Cycles Faster Than Erdos--Posa
This page was built for publication: Large-treewidth graph decompositions and applications