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

DOI10.1007/978-3-319-12340-0_20zbMATH Open1406.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)

Abstract: We give an algorithm which for an input planar graph $G$ of $n$ vertices and integer $k$, in $minO(nlo{g}^{3}n),O(n{k}^2)$ time either constructs a branch-decomposition of $G$ with width at most $(2+delta)k$, $delta>0$ is a constant, or a $(k+1)imeslceilfrack+12ceil$ cylinder minor of $G$ implying $bw(G)>k$, $bw(G)$ is the branchwidth of $G$. This is the first $ildeO(n)$ time constant-factor approximation for branchwidth/treewidth and largest grid/cylinder minors of planar graphs and improves the previous $minO(n^{1+epsilon}),O(n{k}^2)$ ($epsilon>0$ is a constant) time constant-factor approximations. For a planar graph $G$ and $k=bw(G)$, a branch-decomposition of width at most $(2+delta)k$ and a $gimesfracg2$ cylinder/grid minor with $$, $$ is constant, can be computed by our algorithm in $minO(nlo{g}^{3}nlogk),O(n{k}^{2}logk)$ time.

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)

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

Related Items (4)

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 ⋮ Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n 1 + ε ) Time

Recommendations

• Unnamed Item 👍 👎
• Approximate tree decompositions of planar graphs in linear time 👍 👎
• 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 👍 👎
• Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs 👍 👎
• Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n 1 + ε ) Time 👍 👎
• Optimal branch-decomposition of planar graphs in O ( n ³ ) Time 👍 👎
• Empirical Study on Branchwidth and Branch Decomposition of Planar Graphs 👍 👎
• Automata, Languages and Programming 👍 👎
• Algorithms - ESA 2003 👍 👎

This page was built for publication: Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs