Abstract
For oriented graphs G and H, a homomorphism f : G -> H is locally-injective if, for every v is an element of V (G), it is injective when restricted to some combination of the in-neighbourhood and out-neighbourhood of v. Two of the possible definitions of local-injectivity are examined. In each case it is shown that the associated homomorphism problem is NP-complete when H is a reflexive tournament on three or more vertices with a loop at every vertex, and solvable in polynomial time when H is a reflexive tournament on two or fewer vertices.
| Originalsprog | Engelsk |
|---|---|
| Artikelnummer | 4 |
| Tidsskrift | Discrete Mathematics & Theoretical Computer Science |
| Vol/bind | 20 |
| Udgave nummer | 2 |
| Antal sider | 22 |
| ISSN | 1462-7264 |
| Status | Udgivet - 2018 |
Fingeraftryk
Dyk ned i forskningsemnerne om 'Complexity of locally-injective homomorphisms to tournaments'. Sammen danner de et unikt fingeraftryk.Citationsformater
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver