Vaš brskalnik ne omogoča JavaScript!
JavaScript je nujen za pravilno delovanje teh spletnih strani. Omogočite JavaScript ali pa uporabite sodobnejši brskalnik.
Repozitorij Univerze v Ljubljani
Nacionalni portal odprte znanosti
Odprta znanost
DiKUL
slv
|
eng
Iskanje
Napredno
Novo v RUL
Kaj je RUL
V številkah
Pomoč
Prijava
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
)
PDF - Predstavitvena datoteka,
prenos
(707,86 KB)
MD5: F60456E2307A5273935A869DD2E1500F
URL - Izvorni URL, za dostop obiščite
https://www.sciencedirect.com/science/article/pii/S0166218X25004512
Galerija slik
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
UDK:
519.17
ISSN pri članku:
0166-218X
DOI:
10.1016/j.dam.2025.08.006
COBISS.SI-ID:
245924099
Datum objave v RUL:
17.10.2025
Število ogledov:
564
Število prenosov:
271
Metapodatki:
Citiraj gradivo
Navadno besedilo
BibTeX
EndNote XML
EndNote/Refer
RIS
ABNT
ACM Ref
AMA
APA
Chicago 17th Author-Date
Harvard
IEEE
ISO 690
MLA
Vancouver
:
Kopiraj citat
Objavi na:
Gradivo je del revije
Naslov:
Discrete applied mathematics
Skrajšan naslov:
Discrete appl. math.
Založnik:
Elsevier
ISSN:
0166-218X
COBISS.SI-ID:
25342464
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