APPROXIMATION ALGORITHMS FOR DISTANCE-2 EDGE COLORING.
Christopher L. Barrett, Gabriel Istrate, Anil Kumar Vilikanti, MADHAV V. MARATHE, Shripad Thite · University of North Texas Digital Library (University of North Texas) · 2002
The authors consider the link scheduling problem for packet radio networks which is assigning channels to the connecting links so that transmission may proceed on all links assigned the same channel simultaneously without collisions. This problem can be cast as the distance-2 edge coloring problem, a variant of proper edge coloring, on the graph with transceivers as vertices and links as edges. They present efficient approximation algorithms for the distance-2 edge coloring problem for various classes of graphs.