The complexity of cover graph recognition for some varieties of finite lattices

DOI10.1007/BF01110379zbMath0840.06009OpenAlexW410947548MaRDI QIDQ1908932

Lubos Thoma, Vojtěch Rödl

Publication date: 5 May 1996

Published in: Order (Search for Journal in Brave)

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

zbMATH Keywords

NP-completedecision problemfinite latticecover graphexpander graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Structure theory of lattices (06B05) Varieties of lattices (06B20)

Related Items (1)

$st$-Orientations with Few Transitive Edges

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Edge disjoint placement of graphs
• Ramanujan graphs
• Complexity of diagrams
• On the complexity of diagram testing
• Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
• There are infinitely many Carmichael numbers
• On the hardness of approximating minimization problems
• Undirected Graphs Realizable as Graphs of Modular Lattices

This page was built for publication: The complexity of cover graph recognition for some varieties of finite lattices