Discrete Structures & Graph Algorithms

← Back to Domain-Specific Families

Abstractions about trees, graph decompositions, decision diagrams, ordering, set structures, and algorithms for connectivity, joins, decoding, and distributed coordination.

17 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

• Algebraic Decision Diagram — A reduced ordered binary decision DAG whose terminal nodes carry values from a finite domain not restricted to Boolean values, canonically representing a multivalued function for a fixed variable order.
• Aztec Diamond — Use an order-indexed diamond-shaped square-lattice region whose domino exact covers support a power-of-two enumeration, reversible shuffling, path representations, and an arctic-circle limit shape.
• Disjoint-Set Data Structure — Maintain a mutable partition under Make-Set, Find, and Union, typically with representative-rooted forests, union by rank or size, and path compression for inverse-Ackermann amortized time.
• Finite subdivision rule — A finite recursive prescription replacing each tile type by a patterned subdivision to generate successively finer cell structures.
• Graph Duality — Pair a planar graph with a dual by placing a vertex inside each face and joining faces that share an edge, so vertices swap with faces and problems translate across a lossless table — paths become cuts, colorings become face colorings — letting you solve whichever side is easier.
• Graph-Structured Stack — Represent many simultaneously live stack histories as a shared directed acyclic graph whose paths encode stacks, whose frontier nodes are tops, and whose split, merge, and pop operations avoid duplicating common history during nondeterministic parsing.
• Hadwiger number — The largest integer k such that the complete graph on k vertices occurs as a minor of a given undirected graph.
• Multitree — A directed acyclic graph in which every ordered pair of vertices has at most one directed path, equivalently a DAG whose reachability order is diamond-free.
• NAND Logic — A basis-restricted Boolean construction in which every target function is synthesized as a composition of NAND alone, exploiting NAND's functional completeness.
• Natural Number — The successor-generated arithmetic carrier for finite counting and ordinal indexing, equipped with induction and recursion from a distinguished first element.
• Topological Sorting — Produce a linear order over the nodes of a directed acyclic graph so every edge runs forward — every dependency before its dependent — by repeatedly emitting any node with no unmet prerequisite, well-defined exactly when the graph has no cycle.
• Tree (Data Structure) — The computer-science container for rooted, single-parent, acyclic hierarchies whose recursive type lets every algorithm decompose as act-at-the-root, recurse-on-each-subtree, combine — with operation cost governed by one quantity, the tree's height.
• Tree (Graph Theory) — Characterize a connected acyclic graph — equivalently, one with a unique path between every pair of vertices, or exactly n−1 edges on n vertices — so that recognizing the structure by any one handle imports the bridge-everywhere, fundamental-cycle, and cheapest-connector consequences for free.
• Tree (Set Theory) — Organize a partially ordered set so every node's strict predecessors form a well-order, turning ancestry into ordinal height while allowing branching and transfinite limit levels.
• Yannakakis Algorithm for Acyclic Joins — Evaluate an alpha-acyclic relational join by propagating semijoins up and down a join tree to remove every dangling tuple, then joining or enumerating the reduced relations with input-plus-output cost for a fixed full query.
• Yo-Yo Leader-Election Algorithm — A distributed leader-election protocol repeatedly propagates minimum identifiers forward through an oriented graph and returns yes/no decisions backward to eliminate candidates and prune the graph.
• Zémor's Decoding Algorithm — An alternating hard-decision decoder for Zémor expander codes that repeatedly projects all local edge words on one side of a regular bipartite graph to a nearest component-code word, then switches sides, with spectral expansion giving a logarithmic-round error-correction guarantee.