On the complexity of diagram testing

DOI10.1007/BF01108825zbMath0808.06003MaRDI QIDQ1319079

Graham R. Brightwell

Publication date: 15 March 1995

Published in: Order (Search for Journal in Brave)

zbMATH Keywords

diagramNP-completenessfinite posetorientation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Partial orders, general (06A06) Structural characterization of families of graphs (05C75)

Related Items

Planar posets, dimension, breadth and the number of minimal elements ⋮ On the complexity of cover-incomparability graphs of posets ⋮ Word-Representable Graphs: a Survey ⋮ The complexity of cover graph recognition for some varieties of finite lattices ⋮ Tree-width and dimension ⋮ The number of dependent arcs in an acyclic orientation ⋮ Comparability graphs among cover-incomparability graphs ⋮ $st$-Orientations with Few Transitive Edges ⋮ Semi-transitive orientations and word-representable graphs ⋮ Enumerating \(k\)-arc-connected orientations ⋮ Non-cover generalized Mycielski, Kneser, and Schrijver graphs ⋮ Dimension and height for posets with planar cover graphs. ⋮ Outerstring Graphs are $\chi$-Bounded ⋮ Independent arcs of acyclic orientations of complete \(r\)-partite graphs

Cites Work

• On graphs that can be oriented as diagrams of ordered sets
• On reorienting graphs by pushing down maximal vertices
• Balanced graphs and noncovering graphs
• Complexity of diagrams
• On the hardness of approximating minimization problems
• Unnamed Item
• Unnamed Item
• Unnamed Item