Complexity of computation of some functions of graphs

zbMATH Open0813.05060MaRDI QIDQ3364155FDOQ3364155

Authors: N. I. Glebov, Alexandr Kostochka 

Publication date: 1991

Recommendations

• scientific article; zbMATH DE number 2188410
• The complexity of finite graphs
• Computational complexity of graphs
• On Graph Complexity
• Publication:3201758

zbMATH Keywords

NP-hardHadwiger numberpseudo-achromatic number

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cited In (10)

• Decompositions of graphs of functions and fast iterations of lookup tables
• A Note on The Functions Which Are Not Polynomial Time Computable From Their Graphs
• Estimation of expressions' complexities for two-terminal directed acyclic graphs
• Complexity aspects of the computation of the rank of a graph
• Graph complexity and slice functions
• Title not available (Why is that?)
• On the hardness of computing maximum self-reduction sequences
• Comparison between the complexity of a function and the complexity of its graph
• The weighted complexity and the determinant functions of graphs
• Computational complexity of graphs

This page was built for publication: Complexity of computation of some functions of graphs

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