Zur Seitennavigation oder mit Tastenkombination für den
accesskey
-Taste und Taste 1
Zum Seiteninhalt oder mit Tastenkombination für den
accesskey
und Taste 2
S
tartseite
A
nmelden
Hilfe
Sitemap
Impressum
Datenschutz
node2
Studentisches Leben
Veranstaltungen
Einrichtungen
Räume und Gebäude
Personen
Forschung
Startseite
Publikationen
Publikation: Zeitschriftenartikel
Structure and linear time recognition of 3-leaf powers
Grunddaten
Abstract
Autoren
Einrichtung
Grunddaten
Titel
Structure and linear time recognition of 3-leaf powers
Veröffentlicht in
Information processing letters : devoted to the rapid publication of short contributions to information processing. - Amsterdam [u.a.] : Elsevier
Erscheinungsjahr
2006
Seiten (von – bis)
133 – 138
Band
98
Heft-Nr.
4
Jahr
2006
Publikationsform
Druckschrift
Publikationsart
Zeitschriftenartikel
Sprache
Englisch
Letzte Änderung
20.05.2019 13:41:26
Bearbeitungsstatus
durch UB Rostock abschließend validiert
Dauerhafte URL
http://purl.uni-rostock.de/fodb/pub/36691
Links zu Katalogen
Abstract
A graph G is the k-leaf power of a tree T if its vertices are leaves of T such that two vertices are adjacent in G if and only if their distance in T is at most k. Then T is the k-leaf root of G. This notion was introduced and studied by Nishimura, Ragde, and Thilikos motivated by the search for underlying phylogenetic trees. Their results imply a O(n3) time recognition algorithm for 3-leaf powers. Later, Dom, Guo, Hüffner, and Niedermeier characterized 3-leaf powers as the (bull, dart, gem)-free chordal graphs. We show that a connected graph is a 3-leaf power if and only if it results from substituting cliques into the vertices of a tree. This characterization is much simpler than the previous characterizations via critical cliques and forbidden induced subgraphs and also leads to linear time recognition of these graphs
Autoren
Brandstädt, Andreas
Le, Van Bang
Einrichtung
IEF/Bereich Informatik