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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

Multiplicatively Weighted Centers of Median Graphs in Quasilinear Time

Kriebel Alec
Zenodo (CERN European Organization for Nuclear Research)
Complexity and Algorithms in Graphs
preprint

Multiplicatively Weighted Centers of Median Graphs in Quasilinear Time

Kriebel Alec
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Complexity and Algorithms in Graphs
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.