Complexity of diagrams

DOI10.1007/BF00340774MaRDI QIDQ1316621zbMATH OpenOpenAlexFDO

Authors J. Nešetřil, Vojtěch Rödl

Publication date 16 February 1995

Published in Order (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00340774

zbMATH Keywords

diagramNP-completenessundirected graphfinite posetcovering relation

Mathematics Subject Classification ID

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

Cites work

• A remark on covering graphs
• Combinatorial partitions of finite posets and lattices - Ramsey lattices
• Graph Theory and Probability
• On a Probabilistic Graph-Theoretical Method

Cited in

(21)

• On the complexity of cover-incomparability graphs of posets
• Weakly transitive orientations, Hasse diagrams and string graphs
• Comparability graphs among cover-incomparability graphs
• Efficient polynomial algorithms for distributive lattices
• Cover-incomparability graphs of posets
• Orders with level diagrams
• $st$-Orientations with Few Transitive Edges
• Reorientations of covering graphs
• On edge transitivity of directed graphs
• Inversions, cuts, and orientations
• Contact graphs of boxes with unidirectional contacts
• Planar posets, dimension, breadth and the number of minimal elements
• The complexity of cover graph recognition for some varieties of finite lattices
• Every triangle-free planar graph has a planar upward drawing
• Constructing colorings for diagrams
• On the complexity of diagram testing
• Diagrams, orientations, and varieties
• Tree-width and dimension
• Lattices contained in planar orders are planar
• Covering posets
• Enumerating orientations of ordered sets

This page was built for publication: Complexity of diagrams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1316621)