Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-26437
Titel: Biconnected graph assembly and recognition of DFS trees
Verfasser: Hagerup, Torben
Sprache: Englisch
Erscheinungsjahr: 1985
DDC-Sachgruppe: 004 Informatik
Dokumentart : Report (Bericht)
Kurzfassung: We present two new algorithms on undirected graphs. The first of these takes as input a biconnected graph G and produces a list of simple instructions that may be used to build G from a trivial initial graph in such a way that all intermediate graphs are biconnected. Each instruction specifies either 1) the addition of an edge between two nodes, or 2) the addition of a new node "on" an existing edge. We shall say that the algorithm solves the problem of "biconnected graph assembly". The second algorithm takes as input a connected graph G and a spanning tree T of G given by a marking of the tree edges (i.e., the tree is not rooted). It decides whether there is a depth-first search of G such that the undirected tree implied by the search is identical to T. This may be called "recognition of DFS trees". In fact, the algorithm computes the set of those nodes that may be taken as roots of such a search. Both algorithms are based on depth-first search and work in linear time and space.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-51288
hdl:20.500.11880/26493
http://dx.doi.org/10.22028/D291-26437
Schriftenreihe: Bericht / A / Fachbereich Angewandte Mathematik und Informatik, Universität des Saarlandes
Band: 1985/03
SciDok-Publikation: 2-Apr-2013
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
fb14_1985_03_2.pdf19,49 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.