Presentation
Complexity of Locally Injective Homomorphism to the Theta Graphs
21st International Workshop on Combinatorial Algorithms (IWOCA 2010): Combinatorial Algorithms
(2010)
Abstract
A Theta graph is a multigraph which is a union of at least three internally disjoint paths that have the same two distinct end vertices. In this extended abstract we show full computational complexity characterization of the problem of deciding the existence of a locally injective homomorphism from an input graph G to any fixed Theta graph.
Keywords
- computational complexity,
- locally injective homomorphism,
- Theta graph
Disciplines
Publication Date
2010
Location
London, UK
DOI
10.1007/978-3-642-19222-7_33
Comments
The final publication is available at Springer via https://doi.org/10.1007/978-3-642-19222-7_33. Lidicky, Bernard and Marek Tesar, "Complexity of locally injective homomorphism to the Theta graphs," 21st International Workshop on Combinatorial Algorithms IWOCA 2010: Combinatorial Algorithms, July 26-28, 2010, London, UK, Lecture Notes in Computer Science 6460 (2010): 326-336. Posted with permission.
Copyright 2011 Springer-Verlag Berlin Heidelberg
Citation Information
Bernard Lidicky and Marek Tesař. "Complexity of Locally Injective Homomorphism to the Theta Graphs" 21st International Workshop on Combinatorial Algorithms (IWOCA 2010): Combinatorial Algorithms (2010) Available at: http://works.bepress.com/bernard-lidicky/27/