Complexity of computation of some functions of graphs

MaRDI QIDQ3364155zbMATH OpenFDO

Authors N. I. Glebov, Alexandr Kostochka

Publication date 1991

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)

Recommendations

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

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
• Graph complexity and slice functions
• Complexity aspects of the computation of the rank of a graph
• scientific article; zbMATH DE number 3876594 (Why is no real title available?)
• 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)