Computational complexity of graphs

DOI10.1002/9783527670468.CH05zbMATH Open1328.05181OpenAlexW1518577411MaRDI QIDQ3463386FDOQ3463386

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

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

zbMATH Keywords

lower boundsbipartite graphBoolean functionsgraph entropyBoolean matrixconjunctive normal formgraph complexityRamsey graphSylvester graphtransposition principlerectifier networks

Mathematics Subject Classification ID

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

Cited In (17)

• A computational complexity comparative study of graph tessellation problems
• The complexity of searching a graph
• The linear complexity of a graph
• The complexity of finite graphs
• Data complexity measured by principal graphs
• On Graph Complexity
• Complexity of computation of some functions of graphs
• Complexity aspects of the computation of the rank of a graph
• Graph complexity and slice functions
• Title not available (Why is that?)
• A note on counting independent terms in asymptotic expressions of computational complexity
• Computing the Strength of a Graph
• Connections between artificial intelligence and computational complexity and the complexity of graphs
• On the extension complexity of polytopes separating subsets of the Boolean cube
• Comparison between the complexity of a function and the complexity of its graph
• Graph complexity
• Title not available (Why is that?)

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)