Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree |
| |
| Authors: | Olivier Durand de Gevigney Fr??d??ric Meunier Christian Popa Julien Reygner Ayrin Romero |
| |
| Institution: | 1. Laboratoire G-SCOP, Grenoble INP, 46, avenue F??lix Viallet, 38031, Grenoble, France
2. Universit?? Paris-Est, LVMT, 6?C8 avenue Blaise Pascal, Cit?? Descartes, Champs-sur-Marne, 77455, Marne-la-Vall??e cedex 2, France
3. Ecole Polytechnique, 91128, Palaiseau cedex, France
4. Universit?? Paris-Est, CERMICS, 6?C8 avenue Blaise Pascal, Cit?? Descartes, Champs-sur-Marne, 77455, Marne-la-Vall??e cedex 2, France
|
| |
| Abstract: | Let T = (V, A) be a directed tree. Given a collection P{\mathcal{P}} of dipaths on T, we can look at the arc-intersection graph I(P,T){I(\mathcal{P},T)} whose vertex set is P{\mathcal{P}} and where two vertices are connected by an edge if the corresponding dipaths share a common arc. Monma and Wei, who started
their study in a seminal paper on intersection graphs of paths on a tree, called them DE graphs (for directed edge path graphs)
and proved that they are perfect. DE graphs find one of their applications in the context of optical networks. For instance,
assigning wavelengths to set of dipaths in a directed tree network consists in finding a proper coloring of the arc-intersection
graph. In the present paper, we give
| – |
a simple algorithm finding a minimum proper coloring of the paths. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
|
