Open Research Index

Dynamic MCS Ordering Maintenance

Md Thoriqul Islam Thonmay, Gregory Morse

Palomar Registrypalomar/PALOMAR-2026-10-04-000009Oct 15, 2026cs.DSscore 0

A fully-dynamic Maximum-Cardinality-Search (MCS) ordering algorithm that, on a single-edge insertion or deletion into a loop-free undirected graph, scans the affected window between the two endpoints for the first step at which the current ordering's choice stops being a legal MCS pick, and only then regreedies the suffix (probe-then-repair). Correctness - every order produced stays a valid MCS ordering of the updated graph, and in fact equals the from-scratch canonical ordering - is machine-checked in Lean 4 / Mathlib, together with locality (the first position whose choice can change lies…

SourceRepositoryJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/palomar/PALOMAR-2026-10-04-000009
curl -X POST /api/v1/records/palomar/PALOMAR-2026-10-04-000009/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/palomar/PALOMAR-2026-10-04-000009/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'