CCL

Összesen 1 találat.
#/oldal:
Részletezés:
Rendezés:

1.

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ó:
Rekordok letöltése1