Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs

DOI10.1137/0607043zbMath0617.90083OpenAlexW2046904788MaRDI 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 decompositionselection algorithmsuncapacitated plant locationbiconnected series-parallel multigraphsbinary decomposition treesingle source shortest path problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25)

Related Items

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

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