Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs

DOI10.1137/0607043zbMath0617.90083MaRDI QIDQ3754451

Refael Hassin, Arie Tamir

Publication date: 1986

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0607043

zbMATH Keywords

graph decomposition; selection algorithms; uncapacitated plant location; biconnected series-parallel multigraphs; binary decomposition tree; single source shortest path problem

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68Q25: Analysis of algorithms and problem complexity

Related Items

Efficient algorithms for centers and medians in interval and circular-arc graphs, Complexity of finding a join of maximum weight, Backup 2-center on interval graphs, On graph thickness, geometric thickness, and separator theorems, A cubic algorithm for the directed Eulerian subgraph problem, A polynomial time algorithm to compute the connected treewidth of a series-parallel graph, A unifying location model on tree graphs based on submodularity property, On some optimization problems on \(k\)-trees and partial \(k\)-trees, Complexity results for the \(p\)-median problem with mutual communication, Extensive facility location problems on networks: an updated review, Efficient algorithms for center problems in cactus networks, An optimal algorithm for an outerplanar facility location problem with improved time complexity, On the connectedness property of service areas for the Network Facility Location Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Graph minors. I. Excluding a forest
• Minimum cost flow algorithms for series-parallel networks
• A compact labelling scheme for series-parallel graphs
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• Topology of series-parallel networks
• Graph minors. II. Algorithmic aspects of tree-width
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems
• The Recognition of Series Parallel Digraphs
• Linear-time computability of combinatorial problems on series-parallel graphs
• New Bounds on the Complexity of the Shortest Path Problem
• Finding kth paths and p-centers by generating and searching good data structures
• Depth-First Search and Linear Graph Algorithms
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs