Edge coloring a k-tree into two smaller trees
Dilip Chhajed · Networks · 1997
The problem of the edge coloring partial k-tree into two partial p- and q-trees with p, q < k is considered. An algorithm is provided to construct such a coloring with p + q = k. Usefulness of this result in a Lagrangian decomposition framework to solve certain combinatorial optimization problems is discussed. ® 1997 John Wiley & Sons, Inc.