What is the space complexity of the Floyd-Warshall algorithm for all-pairs shortest paths?
Floyd-Warshall maintains a V x V distance matrix D[i][j], requiring O($V^2)$ memory space.
An Eulerian Path in an undirected graph visits every ________ exactly once.
An Eulerian Path traverses every edge of the graph exactly once. A Hamiltonian Path visits every vertex exactly once.
An undirected connected graph has an Eulerian Circuit if and only if:
Euler proved that a connected graph has an Eulerian Circuit if and only if every vertex has an even degree.
An undirected connected graph contains an Eulerian Path (but NOT an Eulerian Circuit) if and only if:
An Eulerian Path exists if and only if exactly 0 or 2 vertices have odd degree. If exactly 2 have odd degree, they serve as start and end vertices.
Finding a Hamiltonian Cycle in a general graph is known to belong to which complexity class?
Determining whether a general graph contains a Hamiltonian Cycle is a famous NP-complete decision problem.