Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs

DOI10.1137/0607043zbMATH Open0617.90083OpenAlexW2046904788MaRDI QIDQ3754451FDOQ3754451

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

Recommendations

• Efficient parallel algorithms for series parallel graphs
• Parallel algorithms for series parallel graphs
• An \(O(Kn \log (Kn))\) algorithm for the \(K\)th best spanning tree in series parallel graphs
• On greedy algorithms for series parallel graphs
• Publication:4489178

Cites Work

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

Cited In (16)

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

This page was built for publication: Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3754451)