On Steiner versions of (bi)connectivity in network problems

Zoekresultaten

Zoekopdracht: faculteit: "FEB" en publicatiejaar: "2004"

Auteurs	A. Volgenant, C.W. Duin
Titel	On Steiner versions of (bi)connectivity in network problems
Tijdschrift	Graphs and Combinatorics
Jaargang	20
Jaar	2004
Nummer	2
Pagina's	263-273
ISSN	09110119
Faculteit	Faculteit Economie en Bedrijfskunde
Instituut/afd.	FEB: Research Institute in Economics and Econometrics Amsterdam (RESAM)
Samenvatting	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.
Soort document	Artikel
Document finder

Gebruik dit adres om naar deze pagina te linken: http://dare.uva.nl/record/160251

Disclaimer/Klachtenregeling
Meent u dat de digitale beschikbaarstelling van bepaald materiaal inbreuk maakt op enig recht dat u toekomt of uw (privacy)belangen schaadt, dan kunt u dit onderbouwd aan de Universiteitsbibliotheek laten weten. Bij een gegronde klacht zal de Universiteitsbibliotheek het materiaal ontoegankelijk maken en/of van de website verwijderen, dan wel samen met u bekijken hoe op een andere manier aan uw klacht tegemoet kan worden gekomen.
Stuurt u hiervoor een e-mail naar: dare@uva.nl, of een brief naar: Bibliotheek van de Universiteit van Amsterdam, afdeling Elektronische Diensten, UvA-DARE, Singel 425, 1012 WP Amsterdam. Er zal dan zo spoedig mogelijk contact met u worden opgenomen.