The complexity of graph problems for succinctly represented graphs

DOI10.1007/3-540-52292-1_20MaRDI QIDQ4694758zbMATH OpenFDO

Authors Antonio Lozano, José L. Balcázar

Publication date 29 June 1993

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-52292-1_20

zbMATH Keywords

adjacency matrixBoolean circuitBoolean functionboundscomplexityNP-completenessregular graphsrepresented graphs

Mathematics Subject Classification ID

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

Recommendations

• The computational complexity of graph problems with succinct multigraph representation
• The complexity of searching succinctly represented graphs
• scientific article; zbMATH DE number 4110112
• On the succinct representation of graphs
• A note on succinct representations of graphs
• Succinct Representations of Arbitrary Graphs
• scientific article; zbMATH DE number 1351076
• scientific article; zbMATH DE number 3876594
• The complexity of finite graphs
• scientific article; zbMATH DE number 3874609

Cited in

(25)

• The complexity of combinatorial problems with succinct input representation
• A bound for the complexity of a simple graph
• Succinct representation, leaf languages, and projection reductions
• On the complexity of data disjunctions.
• Languages represented by Boolean formulas
• Solving computational problems in the theory of word-representable graphs
• Succinct representations of graphs
• scientific article; zbMATH DE number 3874609 (Why is no real title available?)
• scientific article; zbMATH DE number 3876594 (Why is no real title available?)
• The computational complexity of graph problems with succinct multigraph representation
• scientific article; zbMATH DE number 4110112 (Why is no real title available?)
• On symbolic OBDD-based algorithms for the minimum spanning tree problem
• A note on succinct representations of graphs
• CNF and DNF succinct graph encodings
• Automata-Theoretic Model Checking Revisited
• SOFSEM 2006: Theory and Practice of Computer Science
• Representing graphs implicitly using almost optimal space
• Reachability and bounded emptiness problems of constraint automata with prefix, suffix and infix
• Bounded-depth succinct encodings and the structure they imply on graphs
• AI Planning Languages Semantics
• Verified SAT-Based AI Planning
• Upper Bounding Diameters of State Spaces of Factored Transition Systems
• On the succinct representation of graphs
• The complexity of semilinear problems in succinct representation
• Logic vs. complexity theoretic properties of the graph accessibility problem for directed graphs of bounded degree

This page was built for publication: The complexity of graph problems for succinctly represented graphs

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