labeling graph edges

Question

given an undirected graph, the question is to label its edges with three numbers for example two, zero, and one such that the sum of labels of all edges is minimized. Additionally, for every edge that is labeled with zero, there must exist a neighboring edge that is labeled with two. The task is to find the minimum sum of labels for the edges in the given graph.

Answer 1

There is no need for dynamic programming. A straightforward algorithm can do the work.

Note that the edges that connect to leaf nodes MUST be colored 1. If you color such an edge with 0 there is no other edge on the leaf vertex available to be colored 2 ( "for every edge that is colored with 0, there must exist a neighboring edge that is colored with 2." )

• COLOR every edge with 1
• LOOP A
  • SET MAX = 0
  • SET MAXEdge = anything
  • LOOP E over edges with color 1
    • SET S = 0
    • LOOP e over edges to the vertices at each end of E
      • IF e connects to a leaf ( vertex with degree 1 )
        • CONTINUE
      • IF e is not colored 1
        • CONTINUE
      • SET S = S + 1
    • ENDLOOP e
    • IF S > MAX
      • SET MAX = S
      • SET MAXEdge = E
  • ENDLOOP E
  • IF MAX == 0
    • OUTPUT sum of all edge colors
    • STOP
  • COLOR MAXEdge with color 2
  • LOOP e over edges to the vertices at each end of MAXEdge
    • IF e color == 1
      • COLOR e with 0
• ENDLOOP A