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
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
