Optimal branch-decomposition of planar graphs in O ( n 3 ) Time
From MaRDI portal
Publication:4962735
DOI10.1145/1367064.1367070zbMath1445.68165OpenAlexW2048794017MaRDI QIDQ4962735
Publication date: 5 November 2018
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1367064.1367070
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
(Total) vector domination for graphs with bounded branchwidth ⋮ An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs ⋮ Approximate tree decompositions of planar graphs in linear time ⋮ New analysis and computational study for the planar connected dominating set problem ⋮ A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs ⋮ Unnamed Item ⋮ Efficient reassembling of three-regular planar graphs ⋮ Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs ⋮ Tangle bases: Revisited ⋮ Practical algorithms for branch-decompositions of planar graphs ⋮ Branchwidth is \((1, g)\)-self-dual ⋮ A note on planar graphs with large width parameters and small grid-minors ⋮ Catalan structures and dynamic programming in \(H\)-minor-free graphs ⋮ Parameterized complexity of graph planarity with restricted cyclic orders ⋮ Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds ⋮ Confronting intractability via parameters ⋮ Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs ⋮ Computational study on a PTAS for planar dominating set problem ⋮ Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms ⋮ Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time ⋮ The carving-width of generalized hypercubes ⋮ Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs ⋮ C-planarity testing of embedded clustered graphs with bounded dual carving-width ⋮ Orthogonal planarity testing of bounded treewidth graphs ⋮ Subexponential Parameterized Algorithms for Bounded-Degree Connected Subgraph Problems on Planar Graphs ⋮ Computational study on planar dominating set problem ⋮ Unnamed Item ⋮ Unnamed Item
This page was built for publication: Optimal branch-decomposition of planar graphs in O ( n 3 ) Time
