Anzeige
Erschienen in:
1995 | ReviewPaper | Buchkapitel
Complexity of graph covering problems
verfasst von : Jan Kratochvíl, Andrzej Proskurowski, Jan Arne Telle
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
Given a fixed graph H, the H-cover problem asks whether an input graph G allows a degree preserving mapping f∶V(G)→V(H) such that for every v∈V(G), f(N G (v))=N H (f(v)). In this paper, we design efficient algorithms for certain graph covering problems according to two basic techniques. The first one is a reduction to the 2-SAT problem. The second technique exploits necessary and sufficient conditions for the existence of regular factors in graphs. For other infinite classes of graph covering problems we derive NP-completeness results by reductions from graph coloring problems. We illustrate this methodology by classifying all graph covering problems defined by simple graphs with at most 6 vertices.