1. I. Caragiannis, A. Ferreira, C. Kaklamanis, S. Pérennes, and H. Rivano. Fractional Path Coloring in Bounded Degree Trees with Applications. Algorithmica, 2009. Published online: 14 February 2009. (http://dx.doi.org/10.1007/s00453-009-9278-3) (pdf)
   Abstract: This paper studies the natural linear programming relaxation of the path coloring problem. We prove constructively that finding an optimal fractional path coloring is Fixed Parameter Tractable (FPT), with the degree of the tree as parameter: the fractional coloring of paths in a bounded degree trees can be done in a time which is linear in the size of the tree, quadratic in the load of the set of paths, while exponential in the degree of the tree. We give an algorithm based on the generation of an efficient polynomial size linear program. Our algorithm is able to explore in polynomial time the exponential number of different fractional colorings, thanks to the notion of trace of a coloring that we introduce. We further give an upper bound on the cost of such a coloring in binary trees and extend this algorithm to bounded degree graphs with bounded treewidth. Finally, we also show some relationships between the integral and fractional problems, and derive a (1 + 5/3e) ~= 1.61 approximation algorithm for the path coloring problem in bounded degree trees, improving on existing results. This classic combinatorial problem finds applications in the minimization of the number of wavelengths in wavelength division multiplexing (WDM) optical networks.
   

   @ARTICLE{CFK+09,
   
    author = {I. Caragiannis and A. Ferreira and C. Kaklamanis and S. P\'erennes and H. Rivano},
   
    title = {Fractional Path Coloring in Bounded Degree Trees with Applications},
   
    journal = {Algorithmica},
   
    year = {2009},
   
    abstract = {This paper studies the natural linear programming relaxation of the path coloring problem. We prove constructively that finding an optimal fractional path coloring is Fixed Parameter Tractable (FPT), with the degree of the tree as parameter: the fractional coloring of paths in a bounded degree trees can be done in a time which is linear in the size of the tree, quadratic in the load of the set of paths, while exponential in the degree of the tree. We give an algorithm based on the generation of an efficient polynomial size linear program. Our algorithm is able to explore in polynomial time the exponential number of different fractional colorings, thanks to the notion of trace of a coloring that we introduce. We further give an upper bound on the cost of such a coloring in binary trees and extend this algorithm to bounded degree graphs with bounded treewidth. Finally, we also show some relationships between the integral and fractional problems, and derive a (1 + 5/3e) ~= 1.61 approximation algorithm for the path coloring problem in bounded degree trees, improving on existing results. This classic combinatorial problem finds applications in the minimization of the number of wavelengths in wavelength division multiplexing (WDM) optical networks.},
   
    OPTciteulike-article-id = {4062435},
   
    url = {http://dx.doi.org/10.1007/s00453-009-9278-3},
   
    pdf = {ftp://ftp-sop.inria.fr/mascotte/personnel/Herve.Rivano/Biblio/cfkpr09.pdf},
   
    note = {Published online: 14 February 2009},
   
    OPTx-editorial-board={yes},
   
    OPTx-proceedings={yes},
   
    OPTx-international-audience={yes},
   
    
    
   }

1. A. Casteigts, S. Chaumette, and A. Ferreira. Characterizing Topological Assumptions of Distributed Algorithms in Dynamic Networks. In Proc. of 16th Intl. Conference on Structural Information and Communication Complexity (SIROCCO'09), volume 5869 of Lecture Notes in Computer Science, Piran, Slovenia, May 25-27 2009. Springer-Verlag .
   

   @InProceedings{CCF09,
   
    author = {Casteigts, A. and Chaumette, S. and Ferreira, A.},
   
    title = {Characterizing Topological Assumptions of Distributed Algorithms in Dynamic Networks},
   
    booktitle = {Proc. of 16th Intl. Conference on Structural Information and Communication Complexity (SIROCCO'09)},
   
    year = 2009,
   
    month = {May 25-27},
   
    address = {Piran, Slovenia},
   
    series = {Lecture Notes in Computer Science},
   
    volume = {5869},
   
    publisher = {Springer-Verlag}
    
   }

2. A. Ferreira. Road-mapping the Digital Revolution: Visions from COST Foresight 2030 (An exercise in multi-disciplinarity). In Proceedings of IEEE Wireless VITAE'09, Aalborg, Denmark, May 2009. IEEE Press. (pdf)
   Abstract: {From innovation triggered by user virtual communities to remote surgery and new financial instruments, the creative power of individuals is being fostered at proportions previously unseen. The main driver enabling such a pace of innovation, scientific progress, and user adoption is the Digital Revolution. One consequence is that interrelationships between science, technology and society are increasing in complexity and harder to understand. COST Foresight 2030 is an initiative encompassing a set of events designed to explore a multi-disciplinary vision for a future permeated and shaped by the digital revolution. This paper describes the vision behind COST Foresight 2030 and highlights several issues that are likely to become central in the next decades.}
   

   @InProceedings{Fer09,
   
    author = {Ferreira, A.},
   
    title = {Road-mapping the Digital Revolution: Visions from COST Foresight 2030 (An exercise in multi-disciplinarity)},
   
    booktitle = {Proceedings of IEEE Wireless VITAE'09},
   
    year = 2009,
   
    month = {May},
   
    address = {Aalborg, Denmark},
   
    publisher = {IEEE Press},
   
    pdf = {ftp://ftp-sop.inria.fr/mascotte/Publications/Fer09.pdf},
   
    OPTx-editorial-board={yes},
   
    OPTx-proceedings={yes},
   
    OPTx-international-audience={yes},
   
    abstract = {From innovation triggered by user virtual communities to remote surgery and new financial instruments, the creative power of individuals is being fostered at proportions previously unseen. The main driver enabling such a pace of innovation, scientific progress, and user adoption is the Digital Revolution. One consequence is that interrelationships between science, technology and society are increasing in complexity and harder to understand. COST Foresight 2030 is an initiative encompassing a set of events designed to explore a multi-disciplinary vision for a future permeated and shaped by the digital revolution. This paper describes the vision behind COST Foresight 2030 and highlights several issues that are likely to become central in the next decades.} 
    
   }

BACK TO INDEX