Graph Theory
- succinct versions of many graph problems, with graphs represented as Boolean circuits, ordered Binary Decision Diagrams or other related representations:
- s-t reachability problem for succinct graphs. This is essentially the same as the simplest plan existence problem in automated planning and scheduling.
- planarity of succinct graphs
- acyclicity of succinct graphs
- connectedness of succinct graphs
- existence of Eulerian paths in a succinct graph
- Canadian Traveller Problem.
- Determining whether routes selected by the Border Gateway Protocol will eventually converge to a stable state for a given set of path preferences
- Dynamic graph reliability.
- Deterministic Constraint Logic (unbounded)
- Nondeterministic Constraint Logic (unbounded)
- Bounded two-player Constraint Logic
Read more about this topic: List Of PSPACE-complete Problems
Famous quotes containing the words graph and/or theory:
“When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.”
—Marshall McLuhan (1911–1980)
“The great tragedy of science—the slaying of a beautiful theory by an ugly fact.”
—Thomas Henry Huxley (1825–1895)