Találati lista | Tudóstér

001-es BibID:	BIBFORM104107
035-os BibID:	(WoS)000483940500003 (Scopus)85072740831
Első szerző:	Bodirsky, Manuel
Cím:	Constraint Satisfaction Problems for Reducts of Homogeneous Graphs / Manuel Bodirsky, Barnaby Martin, Michael Pinsker, Andras Pongrácz
Dátum:	2019
ISSN:	0097-5397
Megjegyzések:	For n \geq 3, let (Hn, E) denote the nth Henson graph, i.e., the unique countable homogeneous graph with exactly those finite graphs as induced subgraphs that do not embed the complete graph on n vertices. We show that for all structures \Gamma with domain Hn whose relations are first-order definable in (Hn, E) the constraint satisfaction problem for \Gamma either is in P or is NP-complete. We moreover show a similar complexity dichotomy for all structures whose relations are first-order definable in a homogeneous graph whose reflexive closure is an equivalence relation. Together with earlier results, in particular for the random graph, this completes the complexity classification of constraint satisfaction problems of structures first-order definable in countably infinite homogeneous graphs: all such problems are either in P or NP-complete.
Tárgyszavak:	Természettudományok Matematika- és számítástudományok idegen nyelvű folyóiratközlemény külföldi lapban folyóiratcikk constraint satisfaction problems homogeneous structures first-order reducts universal algebra structural Ramsey theory computational complexity
Megjelenés:	Siam Journal On Computing. - 48 : 4 (2019), p. 1224-1264. -
További szerzők:	Martin, Barnaby Pinsker, Michael Pongrácz András (1986-) (matematikus)
Pályázati támogatás:	OTKA-109185 OTKA EFOP-3.6.2-16-2017-00015 EFOP FK 124814 Egyéb PD 125160 Egyéb
Internet cím:	Szerző által megadott URL DOI Intézményi repozitóriumban (DEA) tárolt változat
Borító:
Saját polcon: