Multiplicatively Weighted Centers of Median Graphs in Quasilinear Time
A short capped integral-distance threshold transformation converts multiplicatively weighted vertex-center feasibility to additively weighted eccentricities. Combining it with the credited Berge-Ducoffe-Habib additive algorithm and Ducoffe's known implicit optimization mechanism gives a deterministic O(n log^5(2n)) exact-operation algorithm for a center, optimum radius and all centers on every finite connected simple unit-edge median graph supplied by adjacency lists and promised median. This resolves the finite algorithmic form of Open Problem 1 in Ducoffe's Oberwolfach Report 8/2026, without a cube-dimension bound. Nonnegative finite real profiles are allowed in an exact comparison model; no encoding-independent bit bound, graph recognition, arbitrary edge-length, infinite-encoding or local-unimodality result is claimed. The note credits the earlier cube-free O(n log^2 n) result and makes no novelty claim for the additive algorithm or weighted-median search. Its appendix and verification package give explicit consistent balance-parameter and depth-estimate corrections for two proof issues in arXiv:2410.10235v1, preserving the imported time bound; no claim is made about uninspected final SODA typesetting. Two independent primary-source priority audits found no earlier explicit same-scope resolution, but historical firstness and continued open status are not certified. Inaccessible older tree-center originals, uninspected final SODA typesetting and incomplete indexing bound the audit. The authored-only package preserves original inputs, independent derivations, exact rational finite controls, ordinary nested checksum manifests and an offline replay driver. Brute reference routines are not a fast implementation or an experimental proof of the asymptotic theorem. AI tools were used extensively in solving, development, writing, reproduction and adversarial verification. This is an unrefereed preprint with internal AI adversarial reviews; it has not received human peer review or proof-assistant certification.
Authors
- Kriebel Alec (ORCID: https://orcid.org/0009-0001-9320-500X)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-10-14
- DOI
- https://doi.org/10.5281/zenodo.23385144
- Primary Topic
- Complexity and Algorithms in Graphs
- Type
- preprint