J. Fiala
Comparing universal covers in polynomial time
Fiala, J.; Paulusma, D.
Authors
Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
Contributors
Edward A. Hirsch
Editor
Alexander A. Razboro
Editor
Alexei Semenov
Editor
Anatol Slissenko
Editor
Abstract
The universal cover T G of a connected graph G is the unique (possible infinite) tree covering G, i.e., that allows a locally bijective homomorphism from T G to G. Universal covers have major applications in the area of distributed computing. It is well-known that if a graph G covers a graph H then their universal covers are isomorphic, and that the latter can be tested in polynomial time by checking if G and H share the same degree refinement matrix. We extend this result to locally injective and locally surjective homomorphisms by following a very different approach. Using linear programming techniques we design two polynomial time algorithms that check if there exists a locally injective or a locally surjective homomorphism, respectively, from a universal cover T G to a universal cover T H . This way we obtain two heuristics for testing the corresponding locally constrained graph homomorphisms. As a consequence, we have obtained a new polynomial time algorithm for testing (subgraph) isomorphism between universal covers, and for checking if there exists a role assignment (locally surjective homomorphism) from a given tree to an arbitrary fixed graph H.
Citation
Fiala, J., & Paulusma, D. (2008). Comparing universal covers in polynomial time. In E. A. Hirsch, A. A. Razboro, A. Semenov, & A. Slissenko (Eds.), Computer science – theory and applications, Third International Computer Science Symposium in Russia, CSR 2008, 7-12 June 2008, Moscow, Russia ; proceedings (158-167). https://doi.org/10.1007/978-3-540-79709-8_18
Conference Name | 3rd International Computer Science Symposium in Russia |
---|---|
Conference Location | Moscow, Russia |
Publication Date | Jan 1, 2008 |
Deposit Date | Oct 6, 2010 |
Publisher | Springer Verlag |
Pages | 158-167 |
Series Title | Lecture notes in computer science |
Series Number | 5010 |
Edition | 3rd |
Book Title | Computer science – theory and applications, Third International Computer Science Symposium in Russia, CSR 2008, 7-12 June 2008, Moscow, Russia ; proceedings. |
DOI | https://doi.org/10.1007/978-3-540-79709-8_18 |
Public URL | https://durham-repository.worktribe.com/output/1159609 |
You might also like
Matching cuts in graphs of high girth and H-free graphs
(2023)
Conference Proceeding
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Computing Subset Vertex Covers in H-Free Graphs
(2023)
Conference Proceeding
Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
(2023)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search