Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs

DOI10.1016/j.dam.2018.08.027zbMath1406.05102arXiv1407.6761OpenAlexW2898301962WikidataQ129011837 ScholiaQ129011837MaRDI QIDQ1730234

Gengchun Xu, Qian-Ping Gu

Publication date: 11 March 2019

Published in: Discrete Applied Mathematics, Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1407.6761

zbMATH Keywords

approximation algorithmplanar graphsgrid minorbranch-/tree-decompositions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Approximate tree decompositions of planar graphs in linear time, New analysis and computational study for the planar connected dominating set problem, Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximate tree decompositions of planar graphs in linear time
• A combinatorial optimization algorithm for solving the branchwidth problem
• Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time
• Practical algorithms for branch-decompositions of planar graphs
• Treewidth lower bounds with brambles
• Graph minors. X: Obstructions to tree-decomposition
• Call routing and the ratcatcher
• Quickly excluding a planar graph
• Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs
• Graph minors. XIII: The disjoint paths problem
• Improved bounds on the planar branchwidth with respect to the largest grid minor size
• Planar Branch Decompositions I: The Ratcatcher
• Planar Branch Decompositions II: The Cycle Method
• All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs
• Undirected single-source shortest paths with positive integer weights in linear time
• Easy problems for tree-decomposable graphs
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Complexity of Finding Embeddings in a k-Tree
• Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time
• Constructive linear time algorithms for branchwidth
• Min st -Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time
• Optimal branch-decomposition of planar graphs in O ( n ³ ) Time
• Empirical Study on Branchwidth and Branch Decomposition of Planar Graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Algorithms - ESA 2003