| Abstrakt: | A r-circular edge coloring of a graph G = (V, E) is a mapping c : E -> [0, k), where
for any two adjacent vertices e1 and e2, 1 <= |c(e1)- c(e2)| <= k - 1 and the circular
chromatic index is the infimum over all r, such that G has a r-circular edge coloring.
A circular r-flow is an asigning of an orientation and a flow function f : E -> [1, r - 1]
to the graph, where the flow value of outgoing edges must be equal to the flow value
of incoming edges for every vertex of the graph.
There exists a duality between colorings and nowhere zero flows. Similar duality
exists between circular colorings and r-tensions, that were defined by DeVos.
The concept of balanced valuation r-flows can be used to compute r-tensions using
mixed linear programming solvers.
We make use of this duality to construct an algorithm that computes the circular
chromatic index of a graph. We will then compare the runtime of this algorithm
to a trivial algorithm for computing circular chromatic index that uses mixed linear
programming.
|
|---|