scientific article; zbMATH DE number 3874609

MaRDI QIDQ3340148zbMATH OpenFDO

Authors K. W. Wagner

Publication date 1984

zbMATH Keywords

compact descriptionsgraph accessibility problemgraph colourability problemgraphs with regularities

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 219271
• scientific article; zbMATH DE number 3883612
• Succinct representations of graphs
• scientific article; zbMATH DE number 3874610
• The computational complexity of graph problems with succinct multigraph representation

Cited in

(18)

• The complexity of combinatorial problems with succinct input representation
• A bound for the complexity of a simple graph
• The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
• The complexity of finite graphs
• On the weighted complexity of a regular covering of a graph
• On the complexity of finite subgraphs of the curve graph
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• Emptiness problems for integer circuits
• Equivalence problems for circuits over sets of natural numbers
• Some computational aspects of solvable regular covers of graphs
• scientific article; zbMATH DE number 3874608 (Why is no real title available?)
• scientific article; zbMATH DE number 3874610 (Why is no real title available?)
• scientific article; zbMATH DE number 219271 (Why is no real title available?)
• Balance problems for integer circuits
• Satisfiability of Algebraic Circuits over Sets of Natural Numbers
• Integer circuit evaluation is PSPACE-complete
• Computing vertex resolvability of some regular planar graphs
• On the complexity of some problems related to graph extensions

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 Q3340148)