The searching over separators strategy to solve some NP-hard problems in subexponential time

DOI10.1007/BF01228511zbMath0797.68161OpenAlexW2106183852WikidataQ29037496 ScholiaQ29037496MaRDI QIDQ2366228

R. Z. Hwang, Ruei-Chuan Chang, Richard Chia-Tung Lee

Publication date: 29 June 1993

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01228511

zbMATH Keywords

computational geometryNP-hardnesstraveling salespersondivide-and- conquer strategyseparators strategy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problem, ON THE DISCRETE UNIT DISK COVER PROBLEM, Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane, The Euclidean \(k\)-supplier problem in \(I R^2\), An ETH-Tight Exact Algorithm for Euclidean TSP, Some variations on constrained minimum enclosing circle problem, VARIATIONS OF BASE-STATION PLACEMENT PROBLEM ON THE BOUNDARY OF A CONVEX REGION, Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions, Small spectral gap in the combinatorial Laplacian implies Hamiltonian, Unit disk cover problem in 2D, Open problems around exact algorithms, The within-strip discrete unit disk cover problem, ALMOST OPTIMAL SOLUTIONS TO k-CLUSTERING PROBLEMS, Exact algorithms for the Hamiltonian cycle problem in planar graphs, On the Discrete Unit Disk Cover Problem, Constrained k-Center Problem on a Convex Polygon, The traveling salesman problem with few inner points

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Multidimensional divide-and-conquer
• Finding small simple cycle separators for 2-connected planar graphs
• Planar graphs: Theory and algorithms
• A Dynamic Programming Approach to Sequencing Problems
• On the Complexity of Some Common Geometric Location Problems
• The p-Centre Problem-Heuristic and Optimal Algorithms
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• A Separator Theorem for Planar Graphs
• Worst-Case and Probabilistic Analysis of a Geometric Location Problem
• On the rectangularp-center problem