Solving NP-Hard Problems on Graphs That Are Almost Trees and an Application to Facility Location Problems
From MaRDI portal
Publication:3766845
DOI10.1145/828.322439zbMath0629.68042OpenAlexW1987698099WikidataQ128126939 ScholiaQ128126939MaRDI QIDQ3766845
Uzi Vishkin, Yuri Gurevich, Larry J. Stockmeyer
Publication date: 1984
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/828.322439
NP-complete problemsparallel algorithmsparallel implementationfacility location problempolynomial time algorithmsNP-hard graph problems
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (24)
Efficient algorithms for center problems in cactus networks ⋮ GLOUDS: representing tree-like graphs ⋮ The location of central structures in trees ⋮ Nonserial dynamic programming formulations of satisfiability ⋮ A finite algorithm for the continuousp-center location problem on a graph ⋮ Succinct data structures for series-parallel, block-cactus and 3-leaf power graphs ⋮ The algorithmic use of hypertree structure and maximum neighbourhood orderings ⋮ Efficient algorithms for solving systems of linear equations and path problems ⋮ Covering edges in networks ⋮ Backup 2-center on interval graphs ⋮ Control of Boolean networks: hardness results and algorithms for tree structured networks ⋮ A note on locating a central vertex of a 3-cactus graph ⋮ A minimum length covering subgraph of a network ⋮ Cycle-maximal triangle-free graphs ⋮ Algorithm to find a maximum 2-packing set in a cactus ⋮ The algorithmic use of hypertree structure and maximum neighbourhood orderings ⋮ The backup 2‐center and backup 2‐median problems on trees ⋮ Locating an absolute center on graphs that are almost trees ⋮ Efficient Farthest-Point Queries in Two-terminal Series-parallel Networks ⋮ An optimal algorithm for solving the 1-median problem on weighted 4-cactus graphs ⋮ Exploiting Structure: Location Problems on Trees and Treelike Graphs ⋮ Approximability issues of guarding a set of segments ⋮ Solving NP-hard problems in 'almost trees': vertex cover ⋮ A linear-time algorithm for solving the center problem on weighted cactus graphs
This page was built for publication: Solving NP-Hard Problems on Graphs That Are Almost Trees and an Application to Facility Location Problems
