The complexity of searching succinctly represented graphs
Publication:4645179
DOI10.1007/3-540-60084-1_75zbMath1412.68077OpenAlexW1516116165MaRDI QIDQ4645179
Publication date: 10 January 2019
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-60084-1_75
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (1)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of combinatorial problems with succinct input representation
- How easy is local search?
- The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
- Space-bounded reducibility among combinatorial problems
- Complete problems for deterministic polynomial time
- On the complexity of the parity argument and other inefficient proofs of existence
- A new variant of the \(A^*\)-algorithm which closes a node at most once.
- Relationships between nondeterministic and deterministic tape complexities
- Constant Depth Reducibility
- Succinct representations of graphs
- Provably Difficult Combinatorial Games
- Alternation
- On Some Deterministic Space Complexity Problems
- The Complexity of the Lin–Kernighan Heuristic for the Traveling Salesman Problem
- New problems complete for nondeterministic log space
- A note on succinct representations of graphs
This page was built for publication: The complexity of searching succinctly represented graphs
