Optimal Reduction of Two-Terminal Directed Acyclic Graphs
- 1 December 1992
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 21 (6) , 1112-1129
- https://doi.org/10.1137/0221065
Abstract
. Algorithms for series-parallel graphs can be extended to arbitrary two-terminal dagsif node reductions are used along with series and parallel reductions. A node reduction contractsa vertex with unit in-degree (out-degree) into its sole incoming (outgoing) neighbor. We give anO(n2:5) algorithm for minimizing node reductions, based on vertex cover in a transitive auxiliarygraph. Applications include the analysis of PERT networks, dynamic programming approaches tonetwork problems, and...Keywords
This publication has 27 references indexed in Scilit:
- Nonconstructive advances in polynomial-time complexityInformation Processing Letters, 1987
- Linear-time computation of optimal subgraphs of decomposable graphsJournal of Algorithms, 1987
- Efficient Algorithms for Optimization and Selection on Series-Parallel GraphsSIAM Journal on Algebraic Discrete Methods, 1986
- Minimum cost flow algorithms for series-parallel networksDiscrete Applied Mathematics, 1985
- An O(|E|) Time Algorithm for Computing the Reliability of a Class of Directed NetworksOperations Research, 1984
- On strictly optimal schedules for the cumulative cost-optimal scheduling problemComputing, 1980
- Scheduling to Minimize Maximum Cumulative Cost Subject to Series-Parallel Precedence ConstraintsOperations Research, 1978
- Computing an st-numberingTheoretical Computer Science, 1976
- Topology of series-parallel networksJournal of Mathematical Analysis and Applications, 1965
- Some properties of line digraphsRendiconti del Circolo Matematico di Palermo Series 2, 1960