A Polynomial-Time Algorithm for the Fractional f-Density
Cherine Fons · container not stated · 2026
Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.
· OpenAlex · dissertation · 2026
Abstract
This thesis studies the exact computation of fractional f-density in loopless multigraphs with positive rational edge weights. Fractional f-density is a weighted density parameter arising in f-edge coloring, where each color may be used at a vertex v up to a prescribed capacity f(v). It gives a structural lower bound for the f-chromatic index and generalizes the classical density parameter from ordinary edge-coloring theory. The method uses a linear-fractional optimization framework whose fixed-threshold subproblems are solved through minimum-cut and minimum T-cut computations on an auxiliary graph.
The analysis supplies an explicit T-cut encoding of the f-parity condition, restores admissibility for relaxed cut solutions, and handles rational edge weights through denominator-clearing integral scaling. The main result gives an exact computation of fractional f-density with a denominator-aware polynomial-time bound in the graph-size and scaled-weight parameters, placing the computation on a rigorous algorithmic foundation.
Open the resolved locator · 10.57709/331
Metadata licence: OpenAlex metadata (CC0)