Találati lista | Tudóstér

001-es BibID:	BIBFORM116541
035-os BibID:	(WoS)001104140800010 (Scopus)85176758065
Első szerző:	Kusper Gábor (informatikus)
Cím:	Using extended resolution to represent strongly connected components of directed graphs / Gábor Kusper, Zijian Győző Yang, Benedek Nagy
Dátum:	2023
ISSN:	1787-5021 1787-6117
Megjegyzések:	In this paper, we study how to represent a directed graph as a SAT problem. We study those directed graphs which consists of two strongly connected components (SCC). We reuse the SAT models which are known as the Black-and-White SAT representations. We present the so-called 3rd Solution Lemma: If a directed graph consists of two SCCs, A and B, and there is an edge from A to B, then the corresponding SAT representation has 3 solutions: the black assignment, the white assignment, and the 3rd solution can be written as not sign A union B. Using this result, we present an important negative result: We cannot represent all SAT problems as directed graphs using the Black-and-White SAT representations. Furthermore, we study the question how to represent an SCC by one Boolean variable to maintain the 3rd Solution Lemma. For that we use extended resolution.
Tárgyszavak:	Műszaki tudományok Informatikai tudományok idegen nyelvű folyóiratközlemény hazai lapban folyóiratcikk boolean logic directed graphs SAT problem
Megjelenés:	Annales Mathematicae et Informaticae. - 58 (2023), p. 92-109. -
További szerzők:	Zijian Győző Yang Nagy Benedek (1973-) (informatikus, matematikus)
Internet cím:	Szerző által megadott URL DOI Intézményi repozitóriumban (DEA) tárolt változat
Borító:
Saját polcon: