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 
Startseite    Anmelden     
Sommer 2024    Hilfe  Trennstrich  Sitemap  Trennstrich  Impressum  Trennstrich  Datenschutz  Trennstrich  node2  Trennstrich  Switch to english language

Publikation: Zeitschriftenartikel

Structure and linear time recognition of 3-leaf powers


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 Diese Publikation in der Universitätsbibliographie Diese Publikation im GBV-Katalog

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 Link zur UB Rostock Link zum GBV-Katalog
Le, Van Bang Link zur UB Rostock Link zum GBV-Katalog

Einrichtung

IEF/Bereich Informatik