Set graphs. II. Complexity of set graph recognition and similar problems

Martin Milanic; Romeo Rizzi; Alexandru I. Tomescu

doi:10.1016/j.tcs.2014.06.017

Set graphs. II. Complexity of set graph recognition and similar problems

Martin Milanic, Romeo Rizzi, Alexandru I. Tomescu

Research output: Contribution to journal › Article › Scientific › peer-review

Original language	English
Journal	Theoretical Computer Science
Volume	547
Pages (from-to)	70-81
Number of pages	12
ISSN	0304-3975
DOIs	https://doi.org/10.1016/j.tcs.2014.06.017
Publication status	Published - 28 Aug 2014
MoE publication type	A1 Journal article-refereed

Fields of Science

Acyclic orientation
Extensionality
Set graph
NP-complete problem
#P-complete problem
Hyper-extensional digraph
Separating code
Open-out-separating code
HEREDITARILY FINITE SETS
CODES
EQUIVALENCE
ALGORITHMS
LOGIC
113 Computer and information sciences

Access to Document

10.1016/j.tcs.2014.06.017

Cite this

@article{4c8d76ba4c8f4b7c9eaf24794b663ba5,

title = "Set graphs. II. Complexity of set graph recognition and similar problems",

keywords = "Acyclic orientation, Extensionality, Set graph, NP-complete problem, #P-complete problem, Hyper-extensional digraph, Separating code, Open-out-separating code, HEREDITARILY FINITE SETS, CODES, EQUIVALENCE, ALGORITHMS, LOGIC, 113 Computer and information sciences",

author = "Martin Milanic and Romeo Rizzi and Tomescu, {Alexandru I.}",

year = "2014",

month = aug,

day = "28",

doi = "10.1016/j.tcs.2014.06.017",

language = "English",

volume = "547",

pages = "70--81",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier Scientific Publ. Co",

}

TY - JOUR

T1 - Set graphs. II. Complexity of set graph recognition and similar problems

AU - Milanic, Martin

AU - Rizzi, Romeo

AU - Tomescu, Alexandru I.

PY - 2014/8/28

Y1 - 2014/8/28

KW - Acyclic orientation

KW - Extensionality

KW - Set graph

KW - NP-complete problem

KW - #P-complete problem

KW - Hyper-extensional digraph

KW - Separating code

KW - Open-out-separating code

KW - HEREDITARILY FINITE SETS

KW - CODES

KW - EQUIVALENCE

KW - ALGORITHMS

KW - LOGIC

KW - 113 Computer and information sciences

U2 - 10.1016/j.tcs.2014.06.017

DO - 10.1016/j.tcs.2014.06.017

M3 - Article

SN - 0304-3975

VL - 547

SP - 70

EP - 81

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -