Bounding threshold dimension: realizing graphic Boolean functions as the AND of majority gates

DOI10.1007/978-3-031-15914-5_18arXiv2202.12325OpenAlexW4312302155MaRDI QIDQ6043188

Rogers Mathew, Atrayee Majumder, Mathew C. Francis

Publication date: 5 May 2023

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2202.12325

zbMATH Keywords

treewidthboxicitythreshold graphsthreshold dimensionintersection dimensiondepth-2 circuitsgraphic Boolean functionmajority gates

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The hardness of approximating the boxicity, cubicity and threshold dimension of a graph
• Boxicity, poset dimension, and excluded minors
• A new upper bound for diagonal Ramsey numbers
• Geometric representation of graphs in low dimension using axis parallel boxes
• A special planar satisfiability problem and a consequence of its NP- completeness
• Intersection dimensions of graph classes
• Tree-width, path-width, and cutwidth
• Algorithmic graph theory and perfect graphs
• Threshold graphs and related topics
• Representing graphs as the intersection of cographs and threshold graphs
• Cubicity, degeneracy, and crossing number
• Boxicity and treewidth
• Local boxicity and maximum degree
• The Complexity of the Partial Order Dimension Problem
• Bithreshold Graphs
• Graph minors. II. Algorithmic aspects of tree-width
• The dimension of random ordered sets
• Paths in graphs