ISSN:
1436-5057
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
Beschreibung / Inhaltsverzeichnis:
Zusammenfassung IstG ein zweifach zusammenhängender Graph mit zwei verschiedenen Knotens undt, so wird seine Knotenmenge derart zwischens undt angeordnet, daß jeder weitere Knoten zwischen zweien seiner Nachbarn liegt. Es wird ein Algorithmus angegeben, der aus einer einfachen Tiefensuche abs mit einer zusätzlichen Nachbearbeitung besteht, die nur einen Zeit- und Speicheraufwand der Ordnung 0(n) erfordert.
Notizen:
Abstract Given a biconnected graphG and two distinct verticess andt, the vertices ofG are sorted in such a way, thats is first,t is last, and every other vertex is somewhere between two of its neighbours. An algorithm is given which consists of a simple depth-first search starting froms followed by some additional postprocessing. The latter uses only 0(n) time and space.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF02253293
Permalink
