Graph complexity
The authors study (Boolean) complexity of graphs, in analogy to complexity of Boolean functions. The idea is the following. Let V be a set of vertices. A graph on V is a subset of \(V\times V\) and a set of graphs is a subset of P(V\(\times V)\) (P denotes the powerset operation). Let B be a set of (Boolean) set operations and let G be a set of graphs; graphs in G are called generators and B is called the basis. Now, given a graph H (on V) the question is how difficult it is to express H in terms of the G and B. The authors consider two complexity measures, formula size and circuit size with respect to two classes of generators, star graphs and complete bipartite graphs. They prove some lower bounds on the complexity of some explicitly given graphs.
- The complexity of finite graphs
- Graph complexity and slice functions
- On the likelihood of forests
- The landscape of communication complexity classes
- On the CNF-complexity of bipartite graphs containing no squares
- An improved lower bound for multicolor Ramsey numbers and a problem of Erdős
- Lower bounds for multicolor Ramsey numbers
- Data complexity measured by principal graphs
- Complexity aspects of the computation of the rank of a graph
- On Graph Complexity
- Zero-information protocols and unambiguity in Arthur-Merlin communication
- Computational complexity of graphs
- scientific article; zbMATH DE number 1302031 (Why is no real title available?)
- MAX-plus objects to study the complexity of graphs
- Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
- scientific article; zbMATH DE number 7561745 (Why is no real title available?)
- scientific article; zbMATH DE number 7561750 (Why is no real title available?)
- Comparison between the complexity of a function and the complexity of its graph
- Monoidal Width
- The complexity of growing a graph
- Monoidal Width: Capturing Rank Width
- On the extension complexity of polytopes separating subsets of the Boolean cube
- Generalisations of matrix partitions: complexity and obstructions
- Limits of preprocessing
- Boolean circuit complexity and two-dimensional cover problems
- Bounded simultaneous messages
- The conjunctive complexity of quadratic Boolean functions
- The linear complexity of a graph
- Depth-based complexity traces of graphs
This page was built for publication: Graph complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1823693)
