Computational complexity of graphs

DOI10.1002/9783527670468.CH05MaRDI QIDQ3463386zbMATH OpenOpenAlexFDO

Authors Stasys Jukna

Publication date 14 January 2016

Published in Advances in Network Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/9783527670468.ch05

zbMATH Keywords

bipartite graphBoolean functionsBoolean matrixconjunctive normal formgraph complexitygraph entropylower boundsRamsey graphrectifier networksSylvester graphtransposition principle

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On Graph Complexity
• Graph complexity
• The complexity of finite graphs
• Computational complexity of the graph approximation problem
• Complexity of computation of some functions of graphs

Cited in

(20)

• The complexity of finite graphs
• Graph complexity and slice functions
• A note on counting independent terms in asymptotic expressions of computational complexity
• Graph complexity
• A computational complexity comparative study of graph tessellation problems
• Data complexity measured by principal graphs
• Complexity aspects of the computation of the rank of a graph
• scientific article; zbMATH DE number 3876594 (Why is no real title available?)
• Complexity of computation of some functions of graphs
• On Graph Complexity
• Connections between artificial intelligence and computational complexity and the complexity of graphs
• The linear complexity of a graph
• The complexity of searching a graph
• Computing the Strength of a Graph
• scientific article; zbMATH DE number 1236360 (Why is no real title available?)
• scientific article; zbMATH DE number 1332674 (Why is no real title available?)
• Comparison between the complexity of a function and the complexity of its graph
• On the extension complexity of polytopes separating subsets of the Boolean cube
• Applications of random algebraic constructions to hardness of approximation
• Boolean circuit complexity and two-dimensional cover problems

This page was built for publication: Computational complexity of graphs

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