Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Fast Algorithm for Rank-Width
verfasst von : Martin Beyß
Erschienen in: Mathematical and Engineering Methods in Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Inspired by the heuristic algorithm for boolean-width by Telle et. al. [1], we develop a heuristic algorithm for rank-width. We compare results on graphs of practical relevance to the established bounds of boolean-width. While the width of most graphs is lower than the known values for tree-width, it turns out that the boolean-width heuristic is able to find decompositions of significantly lower width. In a second step we therefore present a further algorithm that can decide if for a graph
G
and a value
k
exists a rank-decomposition of width lower than
k
. This enables to show that boolean-width is in fact lower than or equal to rank-width on many of the investigated graphs.