Strong Edge Coloring for Channel Assignment in Wireless Radio Networks

2006/03/30 by Christopher L. Barrett, V. S. Anil Kumar, Madhav Marathe +2 · 2 citations
Computer Science · #Cooperative Communication and Network Coding #Mobile Ad Hoc Networks #Wireless Networks and Protocols #Enhanced Data Rates for GSM Evolution #Computer science #Channel (broadcasting) #Wireless #Computer network #Radio networks #Wireless network #Radio resource management #Telecommunications

paper · doi:10.1109/percomw.2006.129

openalex publication_date 2006/03/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

We give efficient sequential and distributed approximation algorithms for strong edge coloring graphs modeling wireless networks. Strong edge coloring is equivalent to computing a conflict-free assignment of channels or frequencies to pairwise links between transceivers in the network

Citations

• Distance-2 Edge Coloring is NP-Complete
• Efficient Vertex- and Edge-Coloring of Outerplanar Graphs
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• The capacity of wireless networks

Cited by

• Strong chromatic index of K 1 , t -free graphs
• Edge coloring [wikipedia]