2005 | OriginalPaper | Buchkapitel
Recognizing HHDS-Free Graphs
verfasst von : Stavros D. Nikolopoulos, Leonidas Palios
Erschienen in: Graph-Theoretic Concepts 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
In this paper, we consider the recognition problem on the HHDS-free graphs, a class of homogeneously orderable graphs, and we show that it has polynomial time complexity. In particular, we describe a simple
O
(
n
2
m
)-time algorithm which determines whether a graph
G
on
n
vertices and
m
edges is HHDS-free. To the best of our knowledge, this is the first polynomial-time algorithm for recognizing this class of graphs.