Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
Prime factorisation of stable-matching instances: uniqueness, simultaneous products, and an exact census
Yoshiteru Ishida
Every balanced instance of the stable marriage problem with strict complete preferences has a unique finest partition into prime blocks, and that single partition simultaneously fa…
cs.DS2026
A Reachable-State Operator Formulation of Deferred Acceptance: Progress Invariants and Structural Diagnostics
Yoshiteru Ishida
We give a reachable-state operator formulation of one-to-one deferred acceptance with strict, possibly incomplete preference lists. A local update operator is defined for each acti…