Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs
DOI10.1137/0607043zbMATH Open0617.90083OpenAlexW2046904788MaRDI QIDQ3754451FDOQ3754451
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
Recommendations
graph decompositionselection algorithmsuncapacitated plant locationbiconnected series-parallel multigraphsbinary decomposition treesingle source shortest path problem
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25)
Cites Work
- Title not available (Why is that?)
- Depth-First Search and Linear Graph Algorithms
- Graph minors. II. Algorithmic aspects of tree-width
- An Algorithmic Approach to Network Location Problems. I: Thep-Centers
- Title not available (Why is that?)
- Minimum cost flow algorithms for series-parallel networks
- The Recognition of Series Parallel Digraphs
- Finding kth paths and p-centers by generating and searching good data structures
- Graph minors. I. Excluding a forest
- The complexity of selection and ranking in X+Y and matrices with sorted columns
- An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems
- Topology of series-parallel networks
- New Bounds on the Complexity of the Shortest Path Problem
- A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
- Linear-time computability of combinatorial problems on series-parallel graphs
- A compact labelling scheme for series-parallel graphs
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)
