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

Martin Milanic, Romeo Rizzi, Alexandru I. Tomescu

Research output: Contribution to journalArticleScientificpeer-review

Original languageEnglish
JournalTheoretical Computer Science
Volume547
Pages (from-to)70-81
Number of pages12
ISSN0304-3975
DOIs
Publication statusPublished - 28 Aug 2014
MoE publication typeA1 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

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 = "8",
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",

}

Set graphs. II. Complexity of set graph recognition and similar problems. / Milanic, Martin; Rizzi, Romeo; Tomescu, Alexandru I.

In: Theoretical Computer Science, Vol. 547, 28.08.2014, p. 70-81.

Research output: Contribution to journalArticleScientificpeer-review

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

VL - 547

SP - 70

EP - 81

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -