Name
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... |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1137/0221065 | SIAM J. Comput. |
Keywords | Field | DocType |
acyclic graph,optimal reduction,directed acyclic graph,vertex cover,dynamic programming,triconnected components,reliability,complexity,algorithms,np completeness,network dynamics | Discrete mathematics,Dynamic programming,Combinatorics,Vertex (geometry),Vertex (graph theory),Series-parallel graph,Directed graph,Directed acyclic graph,SPQR tree,Vertex cover,Mathematics | Journal |
Volume | Issue | ISSN |
21 | 6 | 0097-5397 |
Citations | PageRank | References |
36 | 5.00 | 13 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wolfgang W. Bein | 1 | 194 | 29.68 |
| J Kamburowski | 2 | 189 | 20.86 |
| Matthias F. M. Stallmann | 3 | 166 | 19.38 |