go-v.orgdoi

A Polynomial-Time Algorithm for the Fractional f-Density

Cherine Fons · container not stated · 2026

  • DOI 10.57709/331
  • Publisher OpenAlex
  • Type dissertation
  • Issued 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)

Registry
OpenAlex DOI index + API
Fetched
2026-11-20 05:09 UTC
Cache state
not cached yet (bulk-index+openalex)
Locator
https://hdl.handle.net/20.500.14694/16496
Metadata licence
OpenAlex metadata (CC0)
Scope
Metadata as returned by the resolver; abstracts are never generated here.