Graph Algorithms

← Back to Domain-Specific Abstractions by Domain

4 domain-specific abstractions whose origin domain is Graph Algorithms.

• Euler tour technique — A tree representation that replaces each undirected edge with two directed arcs and linearizes the resulting Euler tour for efficient queries and updates.
• Greedy coloring — A sequential graph-coloring algorithm that assigns each vertex the first available color not used by already colored neighbors.
• Planarity testing — The algorithmic decision problem of determining whether a graph admits a crossing-free plane embedding and producing either an embedding or an obstruction.
• Strong connectivity augmentation — Add the fewest or least-cost directed edges to a digraph so every vertex can reach every other, with the unweighted optimum governed by source and sink components of the condensation DAG.