Anzeige
Erschienen in:
1995 | ReviewPaper | Buchkapitel
Dominoes
verfasst von : T. Kloks, D. Kratsch, H. Müller
Erschienen in: Graph-Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
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
A graph is called a domino if every vertex is contained in at most two maximal cliques. The class of dominoes properly contains the class of line graphs of bipartite graphs, and is in turn properly contained in the class of claw-free graphs. We give some characterizations of this class of graphs, show that they can be recognized in linear time, give a linear time algorithm for listing all maximal cliques (which implies a linear time algorithm computing a maximum clique of a domino) and show that the PATHWIDTH problem remains NP-complete when restricted to the class of chordal dominoes.