Izpis gradiva

A+ | A- | | SLO | ENG

Naslov: Complexity of the game connected domination problem Avtorji: ID Iršič Chenoweth, Vesna (Avtor) Datoteke: PDF - Predstavitvena datoteka, prenos (2,00 MB) MD5: 0373E69595C391F11AD370DCAA9742F3   URL - Izvorni URL, za dostop obiščite https://www.sciencedirect.com/science/article/pii/S0304397525004979   Jezik: Angleški jezik Tipologija: 1.01 - Izvirni znanstveni članek Organizacija: IMFM - Inštitut za matematiko, fiziko in mehaniko Povzetek: The connected domination game is a variant of the domination game where the played vertices must form a connected subgraph at all stages of the game. In this paper we prove that deciding whether the game connected domination number is smaller than a given integer is PSPACE-complete using log-space reductions for both Dominator- and Staller-start connected domination game. Ključne besede: connected domination game, complexity, PSPACE-complete Status publikacije: Objavljeno Verzija publikacije: Objavljena publikacija Datum objave: 01.12.2025 Leto izida: 2025 Št. strani: 11 str. Številčenje: Vol. 1057, article no. 115559 PID: 20.500.12556/DiRROS-23810  UDK: 519.17 ISSN pri članku: 0304-3975 DOI: 10.1016/j.tcs.2025.115559  COBISS.SI-ID: 251830531  Opomba: Datum objave v DiRROS: 06.10.2025 Število ogledov: 235 Število prenosov: 98 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: Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Gradivo je del revije

Naslov:	Theoretical computer science
Skrajšan naslov:	Theor. comp. sci.
Založnik:	Elsevier
ISSN:	0304-3975
COBISS.SI-ID:	26525952

Gradivo je financirano iz projekta

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

Licence

Licenca:	CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
Povezava:	http://creativecommons.org/licenses/by/4.0/deed.sl
Opis:	To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.

Sekundarni jezik

Jezik:	Slovenski jezik
Ključne besede:	povezana dominacijska igra, zahtevnost, PSPACE-polno

Nazaj