Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions

DOI10.1007/s00453-009-9296-1zbMath1200.05223OpenAlexW2165094933WikidataQ59567665 ScholiaQ59567665MaRDI QIDQ1957653

Fedor V. Fomin, Frederic Dorn, Eelko Penninkx, Hans L. Bodlaender

Publication date: 27 September 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://dspace.library.uu.nl/handle/1874/22177

zbMATH Keywords

Hamiltonian cycleTraveling salesman problemPlanar graphsTreewidthBranchwidthExact and parameterized algorithms

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Related Items

Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ Surprising Applications of Treewidth Bounds for Planar Graphs ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Graph Minors and Parameterized Algorithm Design ⋮ New analysis and computational study for the planar connected dominating set problem ⋮ Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane ⋮ A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs ⋮ The parameterized complexity of local search for TSP, more refined ⋮ Beyond bidimensionality: parameterized subexponential algorithms on directed graphs ⋮ Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs ⋮ Correlation clustering and two-edge-connected augmentation for planar graphs ⋮ Upward book embeddability of \(st\)-graphs: complexity and algorithms ⋮ Counting cycles on planar graphs in subexponential time ⋮ Exact algorithms for finding longest cycles in claw-free graphs ⋮ An ETH-Tight Exact Algorithm for Euclidean TSP ⋮ Counting cycles on planar graphs in subexponential time ⋮ Unnamed Item ⋮ 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 ⋮ Faster parameterized algorithms for minor containment ⋮ Confronting intractability via parameters ⋮ Fast minor testing in planar graphs ⋮ A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families ⋮ Slightly Superexponential Parameterized Problems ⋮ Toward solving the Steiner travelling salesman problem on urban road maps using the branch decomposition of graphs ⋮ Parameterized complexity of graph planarity with restricted cyclic orders ⋮ The role of planarity in connectivity problems parameterized by treewidth ⋮ Hitting forbidden induced subgraphs on bounded treewidth graphs ⋮ Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs ⋮ Decomposition of Map Graphs with Applications. ⋮ Induced packing of odd cycles in planar graphs ⋮ How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs? ⋮ Subexponential parameterized algorithms for graphs of polynomial growth ⋮ Dynamic programming for graphs on surfaces ⋮ Finding, hitting and packing cycles in subexponential time on unit disk graphs ⋮ Unnamed Item ⋮ Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth ⋮ An improved exact algorithm for TSP in graphs of maximum degree 4 ⋮ An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Subexponential parameterized algorithms
• Graph minors. X: Obstructions to tree-decomposition
• Call routing and the ratcatcher
• Quickly excluding a planar graph
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Graph separators: A parameterized view
• The searching over separators strategy to solve some NP-hard problems in subexponential time
• Exact algorithms for the Hamiltonian cycle problem in planar graphs
• Sur les partitions non croisées d'un cycle. (The non-crossed partitions of a cycle)
• Tour Merging via Branch-Decomposition
• A Dynamic Programming Approach to Sequencing Problems
• New upper bounds on the decomposability of planar graphs
• A Separator Theorem for Planar Graphs
• Applications of a Planar Separator Theorem
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Parameterized complexity: exponential speed-up for planar graph problems
• Algorithms – ESA 2005
• Computational Study on Dominating Set Problem of Planar Graphs
• Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus