Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time (Q553343): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.tcs.2010.07.017
+Normal rank
@@ Property / OpenAlex ID @@
+W2059590924
@@ Property / OpenAlex ID: W2059590924 / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity of Finding Embeddings in a <i>k</i>-Tree
+Normal rank
@@ Property / cites work @@
+Easy problems for tree-decomposable graphs
@@ Property / cites work: Easy problems for tree-decomposable graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for treewidth
@@ Property / cites work: Approximation algorithms for treewidth / rank @@
+Normal rank
@@ Property / cites work @@
+Treewidth lower bounds with brambles
@@ Property / cites work: Treewidth lower bounds with brambles / rank @@
+Normal rank
@@ Property / cites work @@
+Q4291429
@@ Property / cites work: Q4291429 / rank @@
+Normal rank
@@ Property / cites work @@
+A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
+Normal rank
@@ Property / cites work @@
+Constructive linear time algorithms for branchwidth
+Normal rank
@@ Property / cites work @@
+A simple linear algorithm for the edge-disjoint \((s, t)\)-paths problem in undirected planar graphs
+Normal rank
@@ Property / cites work @@
+Q3579494
@@ Property / cites work: Q3579494 / rank @@
+Normal rank
@@ Property / cites work @@
+Q2921728
@@ Property / cites work: Q2921728 / rank @@
+Normal rank
@@ Property / cites work @@
+Improved Approximation Algorithms for Minimum Weight Vertex Separators
+Normal rank
@@ Property / cites work @@
+Q5403052
@@ Property / cites work: Q5403052 / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal branch-decomposition of planar graphs in             <i>O</i>             (             <i>n</i>             <sup>3</sup>             ) Time
+Normal rank
@@ Property / cites work @@
+Improved bounds on the planar branchwidth with respect to the largest grid minor size
+Normal rank
@@ Property / cites work @@
+Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n 1 + ε ) Time
+Normal rank
@@ Property / cites work @@
+Computing the branchwidth of interval graphs
@@ Property / cites work: Computing the branchwidth of interval graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Graph minors. I. Excluding a forest
@@ Property / cites work: Graph minors. I. Excluding a forest / rank @@
+Normal rank
@@ Property / cites work @@
+Graph minors. II. Algorithmic aspects of tree-width
+Normal rank
@@ Property / cites work @@
+Graph minors. X: Obstructions to tree-decomposition
+Normal rank
@@ Property / cites work @@
+Graph minors. XIII: The disjoint paths problem
@@ Property / cites work: Graph minors. XIII: The disjoint paths problem / rank @@
+Normal rank
@@ Property / cites work @@
+Quickly excluding a planar graph
@@ Property / cites work: Quickly excluding a planar graph / rank @@
+Normal rank
@@ Property / cites work @@
+Call routing and the ratcatcher
@@ Property / cites work: Call routing and the ratcatcher / rank @@
+Normal rank
@@ Property / cites work @@
+Algorithms - ESA 2003
@@ Property / cites work: Algorithms - ESA 2003 / rank @@
+Normal rank
@@ Property / cites work @@
+Edge-Disjoint (s,t)-Paths in Undirected Planar Graphs in Linear Time
+Normal rank