Complexity of diagrams
OrderPublished 1 December 1987
Jaroslav Nešetřil, Vojtěch Rödl
Citations33
SJR quartileQ3
SJR score0.40
SNIP0.73
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is proved that three decision problems related to diagrams are NP-complete.
Abstract
A diagram is an undirected graph corresponding to the covering relation of a finite poset. We prove that three decision problems related to diagrams are NP-complete.
Keywords
Computer ScienceMathematics
Proceedings of the American Mathematical SocietyOn a probabilistic graph-theoretical method
60 Citations1978Jaroslav Nešetřil, Vojtěch Rödl
Algebra UniversalisCombinatorial partitions of finite posets and lattices —Ramsey lattices
57 Citations1984Jaroslav Nešetřil, Vojtěch Rödl