Complexity of representation of graphs by set systems
type: Item
instance of: scholarly article
title: Complexity of representation of graphs by set systems
zbMATH Open document ID: 0473.68064
DOI: 10.1016/0166-218X(81)90007-X
author: Svatopluk Poljak
author: Vojtěch Rödl
author: Daniel Turzík
published in: Discrete Applied Mathematics
publication date: 1981-01-01T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 3742646
zbMATH Keywords: NP-complete
zbMATH Keywords: random graphs
MaRDI profile type: Publication
cites work: Q5570136
cites work: Q3941433
cites work: Graphe représentatif des arêtes d'un multigraphe
cites work: Intersection graphs of curves in the plane
cites work: The Representation of a Graph by Set Intersections
cites work: Some simplified NP-complete graph problems
cites work: On colouring random graphs
cites work: Incidence matrices and interval graphs
cites work: Parallel concepts in graph theory
cites work: Q4198056
cites work: Q4142699
cites work: Sur deux propriétés des classes d'ensembles
cites work: The NP-completeness of the bandwidth minimization problem
cites work: On set systems determined by intersections
cites work: Covering edges by cliques with regard to keyword conflicts and intersection graphs
full work available at URL: 0166-218x(81)90007-x
OpenAlex ID: W1965922177
description: scientific article; zbMATH DE number 3742646