Query:
faculty: "FEB" and publication year: "2004"
| Authors | A. Volgenant, C.W. Duin | | Title | On Steiner versions of (bi)connectivity in network problems |
| Journal | Graphs and Combinatorics |
| Volume | 20 |
| Year | 2004 |
| Issue | 2 |
| Pages | 263-273 |
| ISSN | 09110119 |
| Faculty | Faculty of Economics and Business |
| Institute/dept. | FEB: Research Institute in Economics and Econometrics Amsterdam (RESAM) |
| Abstract | The notions of connectivity and biconnectivity can be generalized in the Steiner sense, i.e., they are restricted to a given subset of the vertices of a graph. We illustrate this generalization on two problems. The first problem is the bottleneck biconnected subgraph problem, the second one is the so-called bipartition problem. The adapted algorithms to solve the Steiner versions of these problems exploit depth-first search to attain respectively a running time of O(|E|+|V|log|V|) and O(|E|+|V|) with E denoting the set of edges and V the set of vertices of the given graph. |
| Document type | Article |
| Document finder | 
|
Use this url to link to this page: http://dare.uva.nl/en/record/160251
Contact us about this recordNotify a colleague
Add to bookbag
|
previous
