Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Algorithms for Comparability of Matrices in Partial Orders Imposed by Graph Homomorphisms
verfasst von : Jiří Fiala, Daniël Paulusma, Jan Arne Telle
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
Degree refinement matrices have tight connections to graph homomorphisms that locally, on the neighborhoods of a vertex and its image, are constrained to three types: bijective, injective or surjective. If graph
G
has a homomorphism of given type to graph
H
, then we say that the degree refinement matrix of
G
is smaller than that of
H
. This way we obtain three partial orders. We present algorithms that will determine whether two matrices are comparable in these orders. For the bijective constraint no two distinct matrices are comparable. For the injective constraint we give a PSPACE algorithm, which we also apply to disprove a conjecture on the equivalence between the matrix orders and universal cover inclusion. For the surjective constraint we obtain some partial complexity results.