Spring til hovednavigation Spring til søgning Spring til hovedindhold

Complexity of locally-injective homomorphisms to tournaments

  • Stefan Bard
  • , Thomas Bellitto
  • , Christopher Duffy
  • , Gary MacGilliyray
  • , Feiran Yan
  • University of Victoria
  • University of Saskatchewan
  • Victoria University

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › peer review

95 Downloads (Pure)

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.
OriginalsprogEngelsk
Artikelnummer4
TidsskriftDiscrete Mathematics & Theoretical Computer Science
Vol/bind20
Udgave nummer2
Antal sider22
ISSN1462-7264
StatusUdgivet - 2018

Fingeraftryk

Dyk ned i forskningsemnerne om 'Complexity of locally-injective homomorphisms to tournaments'. Sammen danner de et unikt fingeraftryk.

Citationsformater