scientific article; zbMATH DE number 3874608

zbMATH Open0548.68039MaRDI QIDQ3340147FDOQ3340147

Authors: K. W. Wagner 

Publication date: 1984

Title of this publication is not available (Why is that?)

Recommendations

• scientific article; zbMATH DE number 3874609
• The complexity of finite graphs
• On a certain complexity estimate in graph theory
• On the complexity of identifying strongly regular graphs
• On the regularity problem in Terwilliger graphs
• On the complexity of some problems related to graph extensions
• A complexity problem for Borel graphs
• scientific article
• scientific article; zbMATH DE number 1302031
• On the weighted complexity of a regular covering of a graph

zbMATH Keywords

graph accessibility problemcompact descriptionsgraph colourability problemgraphs with regularities

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cited In (19)

• Parsing Boolean grammars over a one-letter alphabet using online convolution
• The difference and truth-table hierarchies for NP
• A bound for the complexity of a simple graph
• On the complexity of finite subgraphs of the curve graph
• The complexity of finite graphs
• Some computational aspects of solvable regular covers of graphs
• On the complexity of some problems related to graph extensions
• Satisfiability of algebraic circuits over sets of natural numbers
• Hierarchically specified unit disk graphs
• On the weighted complexity of a regular covering of a graph
• Computational complexity of long paths and cycles in faulty hypercubes
• The complexity of membership problems for circuits over sets of integers
• The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
• More complicated questions about maxima and minima, and some closures of NP
• Hierarchically specified unit disk graphs
• Balance problems for integer circuits
• Emptiness problems for integer circuits
• Linear connectivity problems in directed hypergraphs
• Computing vertex resolvability of some regular planar graphs

This page was built for publication:

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