Colouring the interference digraph of a set of requests in a bidirected tree
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911481168134144 |
|---|---|
| author | Boulier, Hugo Coudert, David Havet, Frédéric Pirot, François |
| author_facet | Boulier, Hugo Coudert, David Havet, Frédéric Pirot, François |
| contents | In this paper, we investigate the impact of the broadcast effect arising in filterless optical networks on the computational complexity of the wavelength assignment problem. We model conflicts using an appropriate interference digraph, whose proper colourings correspond to feasible wavelength assignments. Minimizing the number of required wavelengths therefore amounts to determining the chromatic number of this interference digraph. Within this framework, we first present a polynomial-time 2-approximation algorithm for minimizing the number of wavelengths. We then show that the problem is fixed-parameter tractable when parameterized by the number $k$ of available wavelengths. We also derive polynomial-time algorithms for computing the independence and clique numbers of this interference digraph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_02400 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Colouring the interference digraph of a set of requests in a bidirected tree Boulier, Hugo Coudert, David Havet, Frédéric Pirot, François Discrete Mathematics 05C15, 94C15, 68R1 In this paper, we investigate the impact of the broadcast effect arising in filterless optical networks on the computational complexity of the wavelength assignment problem. We model conflicts using an appropriate interference digraph, whose proper colourings correspond to feasible wavelength assignments. Minimizing the number of required wavelengths therefore amounts to determining the chromatic number of this interference digraph. Within this framework, we first present a polynomial-time 2-approximation algorithm for minimizing the number of wavelengths. We then show that the problem is fixed-parameter tractable when parameterized by the number $k$ of available wavelengths. We also derive polynomial-time algorithms for computing the independence and clique numbers of this interference digraph. |
| title | Colouring the interference digraph of a set of requests in a bidirected tree |
| topic | Discrete Mathematics 05C15, 94C15, 68R1 |
| url | https://arxiv.org/abs/2603.02400 |