A compact labeling scheme for series-parallel graphs |
| |
| Authors: | George Steiner |
| |
| Institution: | Management Science and Information Systems Area, Faculty of Business, McMaster University, Hamilton, Ontario, Canada |
| |
| Abstract: | A linear time labeling algorithm is presented for series-parallel graphs. The labels enable us to efficiently implement dynamic programming algorithms for sequencing problems with series-parallel precedence constraints. The labeling scheme can also be used to efficiently count and generate the initial sets, terminal sets and independent sets in transitive series-parallel digraphs and to provide a characterization of the maximal independent sets in transitive digraphs. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
