Podrobno

Trail Trap: a variant of partizan edge geography
ID Buchanan, Calum (Avtor), ID Carr, MacKenzie (Avtor), ID Clifton, Alexander (Avtor), ID Hartke, Stephen G. (Avtor), ID Iršič Chenoweth, Vesna (Avtor), ID Sieger, Nicholas (Avtor), ID Whitman, Rebecca (Avtor)

.pdfPDF - Predstavitvena datoteka, prenos (707,86 KB)
MD5: F60456E2307A5273935A869DD2E1500F
URLURL - Izvorni URL, za dostop obiščite https://www.sciencedirect.com/science/article/pii/S0166218X25004512 Povezava se odpre v novem oknu

Izvleček
We study a two-player game played on undirected graphs called Trail Trap, which is a variant of a game known as Partizan Edge Geography. One player starts by choosing any edge and moving a token from one endpoint to the other; the other player then chooses a different edge and does the same. Alternating turns, each player moves their token along an unused edge from its current vertex to an adjacent vertex, until one player cannot move and loses. We present an algorithm to determine which player has a winning strategy when the graph is a tree and partially characterize the trees on which a given player wins. Additionally, we show that it is NP-hard to determine if Player 2 has a winning strategy on Trail Trap from the starting position, even for connected bipartite planar graphs with maximum degree 4. We determine which player has a winning strategy for certain subclasses of complete bipartite graphs and grid graphs, and we propose several open problems for further study

Jezik:Angleški jezik
Ključne besede:combinatorial games, generalized geography, computational complexity, partizan games, games on graphs
Vrsta gradiva:Članek v reviji
Tipologija:1.01 - Izvirni znanstveni članek
Organizacija:FMF - Fakulteta za matematiko in fiziko
Status publikacije:Objavljeno
Različica publikacije:Objavljena publikacija
Datum objave:01.01.2026
Leto izida:2026
Št. strani:Str. 79-95
Številčenje:Vol. 379
PID:20.500.12556/RUL-175138 Povezava se odpre v novem oknu
UDK:519.17
ISSN pri članku:0166-218X
DOI:10.1016/j.dam.2025.08.006 Povezava se odpre v novem oknu
COBISS.SI-ID:245924099 Povezava se odpre v novem oknu
Datum objave v RUL:17.10.2025
Število ogledov:564
Število prenosov:271
Metapodatki:XML DC-XML DC-RDF
:
Kopiraj citat
Objavi na:Bookmark and Share

Gradivo je del revije

Naslov:Discrete applied mathematics
Skrajšan naslov:Discrete appl. math.
Založnik:Elsevier
ISSN:0166-218X
COBISS.SI-ID:25342464 Povezava se odpre v novem oknu

Licence

Licenca:CC BY-NC-ND 4.0, Creative Commons Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna
Povezava:http://creativecommons.org/licenses/by-nc-nd/4.0/deed.sl
Opis:Najbolj omejujoča licenca Creative Commons. Uporabniki lahko prenesejo in delijo delo v nekomercialne namene in ga ne smejo uporabiti za nobene druge namene.

Projekti

Financer:NSF - National Science Foundation
Številka projekta:1953985

Financer:NSERC - Natural Sciences and Engineering Research Council of Canada
Program financ.:Canadian Graduate Scholarship
Številka projekta:456422823

Financer:Institute for Basic Science
Številka projekta:IBS-R029-C1

Financer:Grant Agency of the Czech Republic
Številka projekta:23-06815M

Financer:ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
Številka projekta:Z1-50003
Naslov:Igra policajev in roparja na grafih in geodetskih prostorih

Financer:ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
Številka projekta:P1-0297
Naslov:Teorija grafov

Financer:ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
Številka projekta:N1-0218
Naslov:Prepletanje geometrije, topologije in algebre v strukturni in topološki teoriji grafov

Financer:ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
Številka projekta:N1-0285
Naslov:Metrični problemi v grafih in hipergrafih

Financer:ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
Številka projekta:N1-0355
Naslov:Prirejanja, transverzale in hipergrafi

Financer:EC - European Commission
Številka projekta:101071836
Naslov:KARST: Predicting flow and transport in complex Karst systems
Akronim:KARST

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Nazaj