Technical Reports produced within CRESCCO.

[2002]   [2003]   [2004]

2002

M. Andreou, D.A Fotakis, S.E. Nikoletseas, V.G. Papadopoulou and P.G. Spirakis.
On Radiocoloring Hierarchically Specified Planar Graphs: PSPACE-completeness and Approximations.
27th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2002.
(WP1, CTI)

M. Andreou and P. Spirakis.
Efficient Colouring of Squares of Planar Graphs.
TR2002/11/01 Computer Technology Institute, Greece, 2002.
(WP1, CTI)

V. Auletta, I. Caragiannis, C. Kaklamanis, and P. Persiano.
Randomized path coloring on binary trees.
Theoretical Computer Science,Vol. 289 (1), pp. 355-399, 2002.
(WP4, UoP, UNISA)

V. Auletta, R. De Prisco, P. Penna, and P. Persiano.
PTAS for scheduling parallel machines owned by selfish agents.
Manuscript in preparation, 2002.
(WP2, UNISA)

E. Bampis, M. Caramia, J. Fiala, A. Fishkin and A. Iovanella.
Scheduling of independent dedicated multiprocessor tasks. 
International Symposium on Algorithms and Computation, ISAAC 2002, Vancouver, LNCS, 2002.
(WP3, CAU) [ps]

J-C. Bermond and D. Coudert. 
Traffic Grooming in Unidirectional WDM Ring Networks using Design Theory.
In IEEE ICC, Anchorage, Alaska, 2003.
(WP4, UNSA/CNRS) [pdf]

J-C. Bermond, D. Coudert, and X. Munoz. 
Traffic Grooming in Unidirectional WDM Ring Networks: The All-to-all Unitary Case.
In The 7th IFIP Working Conference on Optical Network Design & Modelling - ONDM, 2003.
(WP4, UNSA/CNRS) [pdf]

S.Bessy, F.Havet, and J.Palaysi.
Choosability of bipartite graphs with maximum degree δ.
Rapport de recherche INRIA, RR-4522, 2002.
(WP4, CNRS/UNSA)

B. Bui Xuan, A. Ferreira and A. Jarry.
Computing shortest, fastest, and foremost journeys in dynamic networks.
International Journal of Foundations of Computer Science, to appear.
(WP1, CNRS/UNSA)

A. Clementi, G. Huiban, G. Rossi, and Y.C. Verhoeven.
A Performance Analysis of the MST-based Heuristic for the Energy-Efficient Broadcast Problem in Random Wireless Networks.
Proc. of ACM WMAN '03, to appear.
(WP1, Rome)

I. Caragiannis, C. Kaklamanis, E. Papaioannou. 
Efficient On-line Frequency Allocation and Call Control in Cellular Networks. 
Theory of Computing Systems, Vol. 35 (5), pp. 521-543, 2002.
(WP1, UoP) [ps]

I. Caragiannis, C. Kaklamanis, P. Kanellopoulos. 
New Results for Energy-Efficient Broadcasting in Wireless Networks. 
In Proc. of the 13th Annual International Symposium on Algorithms and Computation (ISAAC '02), 
LNCS 2518, Springer, pp. 332-343, 2002.
(WP1, UoP) [ps]

I. Caragiannis, C. Kaklamanis, P. Kanellopoulos. 
A Logarithmic Approximation Algorithm for the Minimum Energy Consumption Broadcast Subgraph Problem. 
Information Processing Letters, 2003, to appear.
(WP1, UoP)

I.Caragiannis and C.Kaklamanis.
Approximate path coloring with application to wavelength assignment in WDM optical networks.
Technical Report, Dept. of Computer Engineering and Informatics, University of Patras, 2002.
(WP4, UoP)

I.Caragiannis, C.Kaklamanis, P. Persiano, and A. Sidiropoulos.
Fractional coloring of symmetric paths on binary trees.
Technical Report, Dept. of Computer Engineering and Informatics, University of Patras, 2002.
(WP4, UoP, UNISA)

D.Coudert and H.Rivano.
Lightpath assignment for multifibers WDM optical networks with wavelength translators.
In IEEE Globecom'02, Taiwan, November 2002. OPNT-01-5.
(WP4, CNRS/UNSA) [pdf]

D.Coudert and H.Rivano.
Routage optique dans les reseaux WDM multifibres avec conversion partielle.
In AlgoTel'02, pages 17-24, Meze, France, may 2002.
(WP4, CNRS/UNSA) [pdf]

A. Clementi, A. Monti, and R. Silvestri. 
Optimal F-Reliable Protocols for the Do-All problem on Single-Hop Wireless Networks. 
Proc. of ISAAC'02, LNCS 2518, 2002.
(WP1, Rome)

A. Clementi, M. Di Ianni, and R. Silvestri. 
The Minimum Broadcast Range Assignment Problem on Linear Multi-Hop Wireless Networks. 
Theoretical Computer Science, to appear.
(WP1, Rome)

A. Clementi, A. Monti, and R. Silvestri. 
Ditributed Broadcast in Radio Networks for Unknown Topology. 
Theoretical Computer Science, to appear.
(WP1, Rome)

A. Clementi, G. Huiban, P. Penna, G. Rossi, Y.C. Verhoeven. 
Some Recent Theoretical Advances and Open Questions on Energy Consumption in Ad-Hoc Wireless Networks. 
Proc. of the III Int. Workshop ARACNE'02, 2002.
(WP1, Rome)

A. Clementi, A. Ferreira, P. Penna, S. Pérennes and R. Silvestri.
The Minimum Range Assignment Problem on Linear Radio Networks.
ALGORITHMICA 35(2): 95-110 (2003).
(WP1, CNRS/UNSA, Rome)

M. Cesati and M. Di Ianni. 
Minimum-Energy Parameterized Problems in (Wireless Network) Graphs. 
Technical report, 2002.
(WP1, Rome)

A. Ferrante and M. Parente.
Existence of Nash Equilibria in Selfish Routing problems. 
Technical report, Dipartimento di Informatica ed Applicazioni "Renato M. Capocelli", Universita di Salerno, 2002.
(WP2, UNISA)

A. Ferreira.
On models and algorithms for dynamic communication networks: The case for evolving graphs.
4 rencontres francophones sur les Aspects Algorithmiques des Telecommunications (ALGOTEL'02)}, 2002.
(WP1, CNRS/UNSA)

A.Ferreira, S.Pérennes, A.Richa, H.Rivano, and N.Stier.
On the design of multifiber WDM networks.
In AlgoTel'02, pages 25-32, Meze, France, May 2002.
(WP4, CNRS/UNSA)

A.Ferreira, S.Pérennes, A.W. Richa, H.Rivano, and N.Stier Moses.
Models, complexity and algorithms for the design of multifiber WDM networks.
In ICT'03, Papeete, French Polynesia, February 2003. To be published.
(WP4, CNRS/UNSA)

A.V. Fishkin, K. Jansen and M. Mastrolilli.
Job shop scheduling with release dates to minimize the average weighted completion time. 
Technical Report, 2002.
(WP3, CAU)

A. Fishkin and G. Zhang. 
On maximizing the throughput of multiprocessor tasks. 
Mathematical Foundations of Computer Science, MFCS 2002, K. Diks and W. Rytter (eds.), Warsaw, LNCS 2420, 2002, 269-279.
(WP3, CAU) [ps]

D. Fotakis, S. Kontogiannis, E. Koutsoupias, M. Mavronicolas, and P. Spirakis.
The Structure and Complexity of Nash Equilibria for a Selfish Routing Game. 
In Proceedings of the 29th International Colloquium on Automata, Languages and  Programming (ICALP 02), LNCS, Springer, pp. 123-134, 2002.
(WP2, CTI)

D.A. Fotakis, S.E. Nikoletseas, V.G. Papadopoulou and P.G. Spirakis.
NP-Completeness Results and Efficient Approximations for Radiocoloring in Planar Graphs. 
Journal of Theoretical Computer Science (to appear in 2003).
(WP1, CTI)

D.A Fotakis, S.E. Nikoletseas, V.G. Papadopoulou and P.G. Spirakis. 
Radiocolorings in Periodic Planar Graphs: PSPACE-Completeness and Efficient Approximations  for the Optimal Range of Frequencies. 
Workshop on Graph Theoretic Concepts 2002 (WG 2002).
(WP1, CTI)

C. Galdi, C. Kaklamanis, M. Montangero, and P. Persiano.
Optimal and approximate station placement in networks (with applications to multicasting and space efficient traversals).
Technical Report, Dept. of Computer Engineering and Informatics, University of Patras, 2002.
(WP4, UoP, UNISA)

G.Huiban, S.Pérennes, and M.Syska.
Traffic grooming in WDM networks with multi-layer switches.
In IEEE ICC, New-York, April 2002.
(WP4, CNRS/UNSA)

K. Jansen and L. Porkolab.
Linear time approximation schemes for scheduling malleable parallel tasks. 
Algorithmica, 32 (2002), 507-520.
(WP3, CAU)

K. Jansen.
Approximate strong separation with application in fractional graph coloring and preemptive scheduling.
Symposium on Theoretical Aspects of Computer Science, STACS 2002, H. Alt and A. Ferreira (eds.), Antibes, LNCS 2285, 2002, 100-111.
(WP3, CAU)

K. Jansen.
Scheduling malleable parallel tasks: An asymptotic fully polynomial time approximation scheme. 
European Symposium on Algorithms, ESA 2002, R. Mohring and R. Raman (eds.), Rome, LNCS 2461, 2002, 562-573.
(WP3, CAU)

K. Jansen and L. Porkolab.
On preemptive resource constrained scheduling: polynomial-time approximations schemes. 
International Conference on Integer Programming and Combinatorial Optimization, IPCO 2002, W. Cook and A. Schulz (eds.), LNCS 2337, 2002, 329-349.
(WP3, CAU)

K. Jansen and R. Solis-Oba.
Scheduling jobs with chain precedence constraints.
Technical report, 2002.
(WP3, CAU)

K. Jansen and G. Zhang.
An approximation algorithm for the multi-cast congestion problem via minimum steiner trees.
In 3rd Workshop on Approximation and Randomized Algorithms in Communication Networks, ARACNE 2002, A. Clementi and L. Gargano (eds.), Rome, Proceedings in Informatics 15, Carleton Scientific}, pages 77-90, 2002.
(WP4, CAU)

K. Jansen and G. Zhang.
Approximation algorithms for general packing problems with modified logarithmic potential function.
In IFIP International Conference on Theoretical Computer Science, TCS 2002, Foundations of information technology in the era of network and mobile computing, R. Baeza-Yates, U. Montanari and N. Santoro (eds.), Montreal, Kluwer Academic Publisher, pages 255-266, 2002.
(WP4, CAU)

K. Jansen and G. Zhang. 
On rectangle packing: maximizing benefits.
Technical report, 2002.
(WP3, CAU)

E. Koutsoupias, M. Mavronicolas, and P. Spirakis.
Approximate Equilibria and Ball Fusion. 
In Proceedings of the 9th International Colloquium on Structural Information and Communication Complexity (SIROCCO), 2002.
(WP2, CTI)

M. Singh, V. K. Prasanna, J. Rolim, C.S. Raghavendra.
Energy efficient collaborative and distributed computation in mesh-like sensor arrays. 
Technical Report, University of Geneva, 2002.
(WP1, Geneva)

D. Ye and G. Zhang. 
On-line scheduling with extendable working time on a small number of machines. 
Information Processing Letters, accepted for publication.
(WP3, CAU)

D. Ye and G. Zhang. 
On-line scheduling of UET parallel jobs with dependencies on 2-dimensional array. 
Technical Report, 2002.
(WP3, CAU)

G. Zhang, X. Cai and C.K. Wong. 
Some results on resource constrained scheduling. 
IIE Transactions, accepted for publication.
(WP3, CAU)

G. Zhang and D. Ye. 
A note on on-line scheduling with partial information. 
Computers and Mathematics with Applications 44 (2002), 539-543.
(WP3, CAU) [ps]

2003

Ageev, A. Fishkin, A. Kononov, and S. Sevastyanov. 
 Open block scheduling in optical communication networks. 
In Proc. of the 1st Workshop on Approximation and On-line Algorithms (WAOA '03), LNCS 2909, Springer, pp. 13-26, 2003. 
 (WP3, WP4, CAU)

C. Ambuehl, A. Clementi, M. Di Ianni, N. Lev-Tov, A. Monti, D. Peleg, G. Rossi, R. Silvestri. 
 Efficient Algorithms for Low-Energy Bounded-Hop Broadcast in Ad-Hoc Wireless Networks. 
 In Proc. of the 21st International Symposium on Theoretical Aspects of Computer Science (STACS '04), 2004, to appear.
 (WP1, Rome) [ps]

C. Ambuehl, A. Clementi, P. Penna, G. Rossi, R. Silvestri. 
 Energy Consumption in Radio Networks: Selfish Agents and Rewarding Mechanisms. 
In Proc. of the 10th International Colloquium on Structural Information and Communication Complexity (SIROCCO '03), Carleton Scientific 17, pp. 1-16, 2003.
 (WP1, WP2, UNISA, Rome) [ps]

C. Ambuehl, A. Clementi, M. Di Ianni, A. Monti, G. Rossi, R. Silvestri. 
 The Range Assignment Problem in Non-Homogeneous Static Ad-Hoc Networks. 
In Proc. of the 4th International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (IPDPS/WMAN '04), 2004, to appear.
 (WP1, Rome) [ps]

M. Andreou, D. Fotakis, S. Nikoletseas, V. Papadopoulou and P. Spirakis. 
 A 3-approximation algorithm for Radiocoloring k-level restricted Hierarchically Specified Planar Graphs. 
 Technical Report, 2003. 
 (WP1, CTI)

M. Andreou, D. Fotakis, S. Nikoletseas, V. Papadopoulou and P. Spirakis.
A 2,66-approximation algorithm for Radiocoloring k-level restricted Hierarchically Specified Planar Graphs.
 Technical Report, 2003.
 (WP1, WP5, CTI) [ps]

M. Andreou, M. Karpinski, V. Papadopoulou and P. Spirakis. 
 Frequency Assignment Problems on VMG-represented graphs. 
 Technical Report, 2003. 
 (WP1, WP5, CTI)

M. Andreou, S. Nikoletseas and P. Spirakis. 
Algorithms and Experiments on Colouring squares of Planar Graphs. 
In Proc. of the 2nd International Workshop on Experimental and Efficient Algorithms (WEA '03), LNCS 2647, pp. 15-32, 2003.
(WP1, WP5, CTI) [ps]

M. Andreou, S. Nikoletseas, V. Papadopoulou, P. Spirakis, V. Theodoridou, A. Xeros. 
 Frequency Assignment Algorithms for Radio and Mobile Networks. 
 Technical Report, 2003. 
 (WP1, WP5, CTI)

E. Angel, E. Bampis, and A. Fishkin. 
 A note on scheduling to meet two min-sum objectives.  
Technical Report, 2003.
 (WP3, CAU)

A. Antoniou, A. Boukerche, I. Chatzigiannakis, G. Mylonas and S. Nikoletseas. 
 A New Energy Efficient and Fault-tolerant Protocol for Data Propagation in Smart Dust Networks using Varying Transmission Range. 
In Proc. of the 37th Annual ACM/IEEE Simulation Symposium (ANSS '04), 2004, to appear. 
(WP1, WP5, CTI) [ps]

G. Arzhantseva, J. Diaz, J. Petit, J. Rolim, M.J. Serna.
Broadcasting on Networks of Sensors Communicating through Directional Antennas.
 International Workshop on Ambient Intelligence Computing,  CTI Press, pp. 1-12, 2003. Ellinika Grammata.
(WP1, WP5, Geneva) [ps]

S. Athanassopoulos, I. Caragiannis, C. Kaklamanis and P. Kanellopoulos. 
Energy-efficient broadcasting in ad hoc wireless networks: experimental results. 
Technical Report, 2003. 
(WP1, WP5, UoP)

V. Auletta, R. De Prisco, P. Penna and P. Persiano
How to Route and Tax Selfish Unsplittable Traffic.
In Proc. of the 16th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '04), pp. 196-205, 2004.
(WP2, WP3, UNISA) [ps]

V. Auletta, R. De Prisco, P. Penna and P. Persiano
The Power of Verification for One-Parameter Agents.
In Proc. of the 31st International Colloquium on. Automata, Languages and Programming (ICALP '04), LNCS 3142, Springer, pp. 171-182, 2004.
(WP2, WP3, UNISA) [ps]

V. Auletta, R. De Prisco, P. Penna and P. Persiano.
Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines.
In Proc. of the 20th International Symposium on Theoretical Aspects of Computer Science (STACS '04), LNCS
2996, pp. 608-619, 2004.
(WP2, WP3, UNISA) [ps] 

J-C.  Bermond, D. Coudert, M-L. Yu. 
On DRC-covering of K_n by Cycles. 
Journal of Combinatorial Designs 11,  pp.100-112, 2003.
(WP4, UNSA/CNRS)

J-C.  Bermond, N. Marlin, D. Peleg, S. Pérennes. 
Directed Virtual Path Layout in ATM networks. 
Theoretical Computer Science 291, pp. 3-28, 2003.
(WP4, UNSA/CNRS)

J-C.  Bermond, O. DeRivoyre, S. Pérennes, M. Syska,
Groupage par tubes. 
In Proc. of AlgoTel '03, pp.169-174, 2003.
(WP4, UNSA/CNRS)

J-C.  Bermond, C. Colbourn, A. Ling, M.L. Yu. 
Grooming in unidirectional rings: K4-e Designs. 
Discrete Mathematics, Lindner's Volume, 2003.
(WP4, UNSA/CNRS)

D. Coudert, X. Munoz. 
Recent Research Developments in Optics. 
Research Signpost, to appear, ch. Graph Theory and Traffic Grooming in WDM Rings.
(WP4, UNSA/CNRS)

J-C.  Bermond, S. Ceroi. 
Minimizing SONET ADMs in unidirectional WDM rings with grooming ratio 3.
Networks 41, 2, pp. 83-86, 2003.
(WP4, UNSA/CNRS)

G. Bongiovanni and P. Penna
XOR-based schemes for fast parallel IP lookups.
In Proc. of the 5th Conference on Algorithms and Complexity (CIAC '03), LNCS 2653, pp. 238-250, 2003. Full version accepted for publication in Theory of Computing Systems, special issue devoted to selected papers from CIAC'03.
(WP5, UNISA) [ps]

M. Bouklit, D. Coudert, J-F. Lalande, and H. Rivano. 
Approximation combinatoire de multiflot fractionnaire: ameliorations.
In Proc. of AlgoTel '03, 2003.
(WP4, WP5, UNSA/CNRS) [pdf]

M. Bouklit, D. Coudert, J-F. Lalande, C. Paul, and H. Rivano. 
Approximate multicommodity flow for WDM networks design.
In Proceedings of the 10th International Colloquium on Structural Information and Communication Complexity (SIROCCO '03), Carleton Scientific 17, pp. 43-56, 2003.
(WP4, WP5, UNSA/CNRS) [pdf]

I. Caragiannis, C. Kaklamanis, P. Persiano, and A. Sidiropoulos
Fractional and Integral Coloring of Locally-Symmetric Sets of Paths on Binary Trees 
In Proc. of the 1st Workshop on Approximation and On-line Algorithms (WAOA '03), LNCS 2909, Springer, pp. 81-94, 2003.
(WP4, UoP, UNISA)[ps]

I. Caragiannis, C. Kaklamanis, and E. Papaioannou
Simple On-line Algorithms for Call Control in Cellular Networks 
In Proc. of the 1st Workshop on Approximation and On-line Algorithms (WAOA '03), LNCS 2909, Springer, pp. 67-80, 2003.  
(WP1, UoP)[ps]

I. Caragiannis, C. Kaklamanis, and P. Kanellopoulos
Power Consumption Problem in Ad Hoc Wireless Networks. 
In Proc. of the 1st Workshop on Approximation and On-line Algorithms (WAOA '03), LNCS 2909, Springer, pp. 252-255, 2003. 
(WP1, UoP)[ps]

I. Caragiannis, C. Kaklamanis, and P. Kanellopoulos
Energy-Efficient Wireless Network Design. 
In Proc. of the 14th Annual International Symposium on Algorithms and Computation (ISAAC '03), LNCS 2906, Springer, pp. 585-594, 2003. 
(WP1, UoP)[ps]

A. Clementi, G. Huiban, P. Penna, G. Rossi, Y. Verhoeven. 
 On the Approximation Ratio of the MST-based Heuristic for the Energy-Efficient Broadcast Problem in Static Ad-Hoc Radio Networks. 
 In Proc. of the 3rd International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (IPDPS/WMAN '03), 2003.
 (WP1, WP5, UNISA, Rome) [ps]

P. Crescenzi, G. Gambosi, G. Nicosia, P. Penna and W. Unger.
On-line load balancing made simple: Greedy strikes back.
In Proceedings of the 30th International Colloquium on Automata, Languages and Programming  (ICALP '03),  LNCS 2719, pp. 1108-1122, 2003.
(WP3, UNISA) [ps] 

C. Efthymiou, S. Nikoletseas and J. Rolim. 
 Energy Balanced Data Propagation in Wireless Sensor Networks. 
 In Proc. of the 4th International Workshop on Algorithms for Wireless, Mobile, Ad-Hoc and Sensor Networks (IPDPS/WMAN '04), 2004, to appear. 
 (WP1, CTI, GENEVA) [ps]

A. Fishkin. 
 Approximation and online algorithms in scheduling and coloring.  
 PhD thesis, University of Kiel, 2003. 
 (WP3, CAU)

A. Fishkin. 
 Packing rectangles: Experimental results. 
 Technical Report, 2003. 
 (WP3, WP4, WP5, CAU)

A. Fishkin, K. Jansen, and M. Mastrolilli. 
 On minimizing average weighted completion time: a PTAS for the job shop problem with release dates. 
In Proc. of the 4th International Symposium on Algorithms and Computation (ISAAC '03), LNCS 2906, pp. 319-328, 2003. 
 (WP3, CAU)

O. Gerber, and K. Jansen. 
 Packing rectangles with large resources. 
 Technical Report, 2003. 
 (WP3, CAU)

K. Jansen, and R. Solis-Oba. 
 Approximation algorithms for scheduling jobs with chain precedence constraints. 
In Proc. of the 5th International Conference on Parallel Processing and Applied Mathematics (PPAM '03), LNCS 3019, 2003, to appear. 
 (WP3, CAU)

K. Jansen, R. Solis-Oba and M. Sviridenko. 
 Makespan minimization in job shops: a linear time approximation scheme. 
 SIAM Journal on Discrete Mathematics 16, pp. 288-300, 2003. 
 (WP3, CAU)

K. Jansen, and H. Zhang. 
 Scheduling malleable tasks with precedence constraints. 
 Technical Report, 2003. 
 (WP3, CAU)

S. Kontogiannis, D. Fotakis and P. Spirakis. 
Selfish unsplittable flows.
Technical report, 2003.
(WP2, CTI)

J.F. Lalande, S. Pérennes, M. Syska. 
Groupage dans les reseaux dorsaux WDM. 
ROADEF 2003, Proceedings in Informatics, 5, Universite d'Avignon et des Pays de Vaucluse, pp. 254-255, Avignon, France, 2003.
(WP4, UNSA/CNRS)

G. Melideo, P. Penna, G. Proietti, R. Wattenhofer, and P. Widmayer. 
Truthful mechanisms for generalized utilitarian problems. 
In Proc. of the 3rd IFIP Internatonal Conference on Theoretical Computer Science (IFIP-TCS '04), Kluwer Academic Publisher, pp. 165-180, 2004. 
(WP2, UNISA) [ps]

S. Nikoletseas, I. Chatzigiannakis, H. Euthimiou, A. Kinalis, A. Antoniou and G. Mylonas. 
 Energy Efficient Protocols for Sensing Multiple Events in Smart Dust Networks. 
 In Proc. of the 2nd International Mobility and Wireless Access Workshop (MobiWac '03), 2003, to appear. 
 (WP1, WP5, CTI) [ps]

S.Nikoletseas, V.Papadopoulou, and P.Spirakis.
Radiocoloring graphs via the probabilistic method. 
In Proc. of the 4th Panhellenic Logic Symposium 2003, pp. 135-140, 2003.
(WP1, CTI) [ps]

P. Penna and C. Ventre
Sharing the Cost of Multicast Transmissions in Wireless Networks.
In Proc. of the 11th Colloquium on Structural Information and Communication Complexity (SIROCCO '04), LNCS 3104, pp. 255-266, 2004.
(WP1, WP2, UNISA) [ps]

P. Penna and C. Ventre
Energy-Efficient Broadcasting in Ad-Hoc Networks: Combining MSTs with Shortest-Path Trees.
In Proc. of  the ACM Workshop on Performance Evaluation of Wireless Ad-Hoc, Sensor, and Ubiquitous Networks (PE-WASUN'04), ACM Press, pp. 61-68, 2004.
(WP1, WP2, WP5, UNISA) [ps] 

H. Rivano. 
Algorithmique et telecommunications: Coloration et multiflot approches et applications aux reseaux d'infrastructure. 
PhD Thesis, Universite de Nice-Sophia Antipolis, November 2003.
(WP4, WP5, UNSA)

M. Singh, V. Prasanna, J. Rolim, C. Raghavendra.
Collaborative and Distributed Computation in Mesh-Like Wireless Sensor Arrays.  
Personal Wireless Communications (PWC '03), LNCS 2775,  pp. 1-11, 2003.
(WP1, GENEVA) [ps]

C. Tadonki and J. Rolim. 
An analytical model for energy minimization. 
Technical Report, 2003.
(WP1, WP5, GENEVA) [ps]

C. Tadonki, J. Rolim, M. Singh, J. Chlebikova. 
Optimal localization is sensor networks.
Technical Report, 2003. 
(WP1, GENEVA, CAU)

C. Tadonki, J. Rolim, M. Singh, and V. Prasanna. 
Combinatorial Techniques for Memory Power State Scheduling in Energy Constrained Systems. 
In Proc. of the 1st Workshop on Approximation and On-line Algorithms (WAOA '03), LNCS 2909, Springer, pp. 265-268, 2003. 
(WP1, GENEVA)

P. Triantffillou, N. Ntarmos, S. Nikoletseas, P. Spirakis. 
 NanoPeer Networks and P2P Worlds. 
In Proc. of the 3rd IEEE International Conference on Peer-to-Peer Computing (P2P '03), IEEE Computer Society, Peer-to-Peer Computing, 0-7695-2023-5, pp. 40-48, 2003.
 (WP1, CTI) [ps]

D. Ye, and G. Zhang. 
 On-line extensible bin packing with unequal bin sizes. 
In Proc. of the 1st Workshop on Approximation and On-line Algorithms (WAOA '03), LNCS 2909, Springer, pp. 235-247, 2003.
 (WP3, CAU)

2004

S. Alouf, E. Altman, J. Galtier, J.F. Lalande, and C. Touati.
Un algorithme d'allocation de bande passante satellitaire.
Technical Report, 2004.
(WP1, UNSA/CNRS)

P. Ambrosio, V. Auletta.
Deterministic Monotone Algorithms for Scheduling on Related Machines.
In Proc. of the 2nd Workshop on Approximation and On-line Algorithms (WAOA '04), LNCS 3351, Springer, pp. 267-280, 2004.
(WP5, WP2, UNISA)

 C. Ambuehl, A.E.F. Clementi, P. Penna, G. Rossi, R. Silvestri.
On the Approximability of the Range Assignment Problem on Radio Networks in Presence of Selfish Agents.
Theoretical Computer Science, to appear.
(WP1, WP2, Rome, UNISA)

 M. I. Andreou   M. Karpinski,   V. G. Papadopoulou  and P. G. Spirakis.
Radiocoloring Succinct Graphs and its relation to MIS on squares of ordinary Graphs.
Technical Report, 2004.
(WP1, CTI) [ps]

 M. I. Andreou,  V. G. Papadopoulou  P. G. Spirakis, B. Theodorides and A. Xeros.  
Generating and Radiocoloring Families of Perfect Graphs.
 Technical Report, 2004.
(WP1, WP5, CTI) [ps]

 S. Athanassopoulos, I. Caragiannis, C. Kaklamanis, P. Kanellopoulos.
Experimental Comparison of Algorithms for Energy-Efficient Multicasting in Ad Hoc Networks.
In Proc. of the 3rd International Conference on AD-HOC Networks & Wireless (ADHOC NOW '04), pp. 183-196, 2004.
(WP1, WP5, UoP)

V. Auletta, R. De Prisco, P. Penna and G. Persiano.
On Designing Truthful Mechanisms for Online Scheduling.
Technical Report, 2004.
(WP2, WP3, UNISA) [ps]

V. Auletta, R. De Prisco, P. Penna and G. Persiano.
Monotone algorithms characterize mechanisms for selfish jobs.
Technical Report, 2004.
(WP2, WP3, UNISA)

V. Auletta, A.V. Fishkin, and G. Persiano.
On gaining a control over two links occupied by selfish agents.
In Models and Algorithms for Planning and Scheduling Problems (MAPSP '05), 2005.
(WP2, WP3, UNISA, CAU)

E. Bampis, A.F.  Fishkin, I. Milis, and R. Sitters.
Batching of bi-processor dedicated tasks.
Technical Report, 2005.
(WP3, CAU)

 J-C. Bermond and L. Braud and D. Coudert.
 Traffic Grooming on the Path.
 Technical Report, 2005.
(WP4, UNSA/CNRS)

 J-C. Bermond, C. J. Colbourn, D. Coudert, G. Ge, A. Ling, and X. Munoz.
 Traffic grooming in unidirectional WDM rings with grooming ratio C=6.
 To appear in SIAM Journal on Discrete Mathematics, 2004.
 (WP4, UNSA/CNRS)

 J.-C. Bermond, F. Havet, and C. D. Tóth.
Fault tolerant on-board networks with priorities.
Technical Report, 2004.
(WP1, UNSA/CNRS)

J-C. Bermond and J. Peters.
Optimal gathering in radio grid with interferences.
Technical Report, 2005.
(WP1, UNSA/CNRS)

 J-C. Bermond and M. L. Yu.
 Vertex disjoint routings of cycles over tori.
 Technical Report, 2004.
(WP4, UNSA/CNRS)

 S. Bessy.
 Un algorithme d'approximation pour le sous-digraphe fortement connexe minimal.
 In Actes de Algotel. INRIA, 2004.
(WP4, UNSA/CNRS)

 H. J. Böckenhauer, D. Bongartz, J. Hromkovivc, R. Klasing, G. Proietti,  S. Seibert, and W. Unger.
 On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality.
 Theoretical Computer Science, 326(1-3), pp. 137-153, 2004.
(WP4, UNSA/CNRS)

 A. Boukerche, I. Chatzigiannakis and S. Nikoletseas.
Efficient Data Propagation Protocols in Wireless Sensor Networks.
Technical Report, 2004.
(WP1,WP5, CTI)
I. Caragiannis, A.V. Fishkin, and C. Kaklamanis.
 On minimizing the number of ADMs in WDM/SONET rings.
 Technical Report, 2004.
(WP4, UoP, CAU)

I. Caragiannis, A. Fishkin, C. Kaklamanis, E. Papaioannou.
On-line algorithms for disk graphs.
In Proc. of the 29th International Symposium on Mathematical Foundations of Computer Science (MFCS '04), LNCS 3153, Springer, pp. 215-226, 2004.
(WP1, UoP, CAU)

I. Caragiannis, A. Fishkin, C. Kaklamanis, E. Papaioannou.
A tight bound for online coloring of disk graphs.
In Proc. of the 12th Colloquium on Structural Information and Communication Complexity (SIROCCO '05), LNCS, Springer, 2005, to appear.
(WP1, UoP, CAU)

I. Caragiannis, C. Kaklamanis, E. Papaioannou.
New Bounds on the Competitiveness of Randomized Online Call Control in Cellular Networks.
Technical Report, 2005.
(WP1, UoP)

A.E.F. Clementi, M. Di Ianni, A. Monti, G. Rossi, R. Silvestri.
Experimental Analysis of Practically Efficient Algorithms for Bounded-Hop Accumulation in Ad-Hoc Wireless Networks.
In Proc. of the 5th International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (IPDPS/WMAN '05), 2005, to appear.
(WP1, WP5, Rome)

A.E.F. Clementi, A. Monti, R. Silvestri.
Round Robin is Optimal for Fault-Tolerant Broadcasting on Wireless Networks.
Journal of Parallel Distributed Computing 64(1), pp. 89-96, 2004.
(WP1, Rome)

A.E.F. Clementi, P. Penna, R. Silvestri.
On the Power Assignment Problem in Radio Networks.
MONET 9(2), pp. 125-140, 2004.
(WP1, Rome, UNISA)

I. Chatzigiannakis and S. Nikoletseas.
A Forward Planning Protocol for Scalable, Energy Efficient and Fault-tolerant Data Propagation in Wireless Sensor Networks.
Technical Report, 2004.
(WP1, WP5, CTI)

S. Choplin, J. Galtier, and S. Pérennes.
Optimal concave costs in the SDH context.
Technical Report RR-5201, INRIA, 2004 route des lucioles - BP 93 - FR-06902 Sophia Antipolis, May 2004.
 Technical Report, 2004
 (WP4, UNSA/CNRS)
S. Choplin, A. Jarry, and S. Pérennes.
Virtual network embedding in the cycle.
Discrete Applied Mathematics, 145(3), pp. 368-375, 2004.
 (WP4, UNSA/CNRS)
C. Cooper, R. Klasing, and T. Radzik.
A randomized algorithm for the joining protocol in dynamic distributed networks.
Technical Report, 2004.
(WP1, UNSA/CNRS)

C. Cooper, R. Klasing, and M. Zito.
Dominating sets in web graphs.
In Proceedings of the Third Workshop on Algorithms and Models for the Web-Graph (WAW '04), LNCS 3243, Springer, pp. 31-43, 2004.
(WP1, UNSA/CNRS)
A. Davert.
Reroutage incrémental sur réseau optique.
Rapport de stage de DEA RSD, Université de Nice Sophia-Antipolis, 2004.
 (WP4, UNSA/CNRS)
A. Ferreira.
Building a reference combinatorial model for manets.
IEEE Network, 18(5), pp. 24-29, 2004.
(WP1, UNSA/CNRS)

A. Ferreira and A. Jarry.
Complexity of minimum spanning tree in evolving graphs and the minimum-energy broadcast routing problem.
In Proc. of Modeling and Optimization in Mobile, Ad-Hoc and Wireless Networks (WiOpt'04), 2004.
(WP1, UNSA/CNRS)

A. Fishkin, O. Gerber, and K. Jansen.
On weighted rectangle packing with large resources.
3rd IFIP Conference on Theoretical Computer Science, TCS 2004, Toulouse, Kluwer Academic Publisher, 2004, 237-250.
(WP3, CAU)


A. Fishkin, O. Gerber, and K. Jansen.
On efficient weighted rectangle packing with large resources.
Technical Report, 2004.
(WP3, CAU)

A. Fishkin, O. Gerber, K. Jansen, and R. Solis-Oba.
On packing squares with resource augmentation: maximizing the profit.
Australasian Computer Science Week, Computing: The Australasian Theory Symposium, (CATS '05), 2005.
(WP3, CAU)

A.V. Fishkin, K. Jansen, S. Sevastanov, and R. Sitters.
Scheduling on identical parallel machines with migration delays.
Technical Report, 2005.
(WP3, CAU)

M. Flammini, R. Klasing, A. Navarra, and S. Pérennes.
Improved approximation results for the minimum energy broadcasting problem.
In 2nd ACM/SIGMOBILE Annual International Joint Workshop on Foundation of Mobile Computing (DIALM-POMC '04), pp. 85-91, ACM Press, 2004.
(WP1, UNSA/CNRS)

S. Funke, A. Kesselman, Z. Lotker, and M. Segal.
Improved algorithms for the connected sensor cover problem.
In Proc. of the 3rd International Conference on AD-HOC Networks & Wireless (ADHOC NOW '04), pp. 56-59, 2004.
(WP1, UNSA/CNRS)

J. Galtier.
Optimizing the ieee 802.11b performance using slow congestion window decrease.
In Proc. of the 16th ITC Specialist Seminar on performance evaluation of wireless and mobile systems, pp. 165-176, 2004.
(WP1, UNSA/CNRS)

J. Galtier.
Real-time resource allocation for leo satellite constellations.
Wireless Networks, 2004, to appear.
(WP1, UNSA/CNRS)

F. Havet and J.-S. Sereni.
Improper colourings and maximum average degree.
Technical Report, 2004.
(WP1, UNSA/CNRS)

F. Havet and M. Wennink.
The push tree problem.
Networks, 44(4), pp. 281-291, 2004.
(WP1, UNSA/CNRS)

 K. Jansen.
Approximation algorithms for the general max-min resource sharing problem: faster and simpler.
In Proc. of the 9th Scandinavian Workshop on Algorithm Theory (SWAT '04), LNCS 3111, Springer, pp. 311-322, 2004.
(WP3, CAU)

K. Jansen.
Approximation algorithms for mixed fractional packing and covering problems.
In Proc. of the 3rd IFIP Conference on Theoretical Computer Science, TCS 2004, Toulouse, Kluwer Academic Publisher, pp. 223-236, 2004. Also, invited talk, to appear in the 2nd Workshop on Approximation and Online Algorithms (WAOA '04), 2004.
(WP3, CAU)

K. Jansen and R. van Stee.
On Strip Packing With Rotations.
In Proceedings of the 37th ACM Symposium on Theory of Computing (STOC '05), 2005, to appear.
(WP3, CAU)

K. Jansen and G. Zhang.
Maximizing the number of packing rectangles.
9th Scandinavian Workshop on Algorithm Theory (SWAT '04), LNCS 3111, 2004, pp. 362-371.
(WP3, CAU)

A. Jarry and Z. Lotker.
Connectivity in evolving graph with geometric properties.
In the Second ACM/SIGMOBILE Annual International Joint Workshop on Foundations of Mobile Computing (Dial MPOMC 04), 2004.
(WP1, UNSA/CNRS)

L. Jouhet.
Protocole cdma pour les réseaux ad hoc.
Technical Report, 2004.
(WP1, UNSA/CNRS)

 R. Klasing and C. Laforest.
Hardness results and approximation algorithms of k-tuple domination in graphs.
Information Processing Letters, 89(2), pp. 75-83, 2004.
(WP1, UNSA/CNRS)

 R. Klasing, Z. Lotker, A. Navarra, and S. Pérennes.
The points and vertices game.
Technical Report, 2004.
(WP1, UNSA/CNRS)

 R. Klasing, A. Navarra, A. Papadopoulos, and S. Pérennes.
Adaptive broadcast consumption (abc), a new heuristic and new bounds for the minimum energy broadcast routing problem.
In Proc. 3rd FIP-TC6 Networking Conference (Networking '04), LNCS 3042, Springer, pp. 866-877, 2004.
(WP1, UNSA/CNRS)

 R. Klasing, N. Morales, S. Perennes.
On the Complexity of Bandwidth Allocation in Radio Networks with Steady Traffic Demands.
Technical Report, 2004.
(WP1, UNSA/CNRS)
G. Kozma, Z. Lotker, M. Sharir, and G. Stupp.
Geometrically aware communication in random wireless networks.
In 24th ACM Symp. on Principles of Distributed Computing, pp. 310-319, 2004.
(WP1, UNSA/CNRS)

J-F. Lalande.
Conception de réseaux de télécommunications: optimisation et expérimentations.
PhD thesis, École doctorale STIC, Université de Nice-Sophia Antipolis, Décembre 2004.
 (WP4, UNSA/CNRS)
J-F. Lalande, M. Syska, and Y. Verhoeven.
Arrondi aléatoire et protection des réseaux WDM.
In 6e congrès de la Société Franc caise de Recherche Opérationnelle et d'Aide à la Décision: ROADEF, Feb 2005.
 (WP4, UNSA/CNRS)
A. Laugier and S. Petat.
Network design and b-matching.
 Technical Report, 2004.
 (WP4, UNSA/CNRS)
P. Leone, S. Nikoletseas and J. Rolim.
An Adaptive Blind Algorithm for Energy Balanced Data Propagation in Wireless Sensors Networks.
 Technical Report, 2004.
(WP1, CTI, GENEVA)

P. Leone and J. Rolim.
Towards a dynamical model for wireless sensor networks.
In Proc. of the Algorithmic Aspects of Wireless Sensor Networks, First International Workshop (ALGOSENSOR '04), 2004.
(WP1, WP5, GENEVA)

Z. Lotker, M. Martinez de Albeniz, and S. Pérennes.
Range-free ranking in sensors networks and its applications to localization.
In Proc. of the 3rd International Conference on AD-HOC Networks & Wireless (ADHOC NOW '04), pp. 158-171, 2004.
(WP1, UNSA/CNRS)

A. Navarra.
Tighter bounds for the minimum energy broadcasting problem.
Technical Report, 2004.
(WP1, UNSA/CNRS)

P. Penna and C. Ventre.
More Powerful and Simpler Cost-Sharing Methods.
In Proc. of the 2nd Workshop on Approximation and On-line Algorithms (WAOA '04), LNCS 3351, Springer, pp. 97-110, 2005.
(WP1, WP2, UNISA) [ps]

P. Penna and C. Ventre.
Free-riders  in Steiner tree cost-sharing games.
In Proc. of the 12th Colloquium on Structural Information and Communication Complexity (SIROCCO '05), LNCS, Springer, 2005, to appear.
(WP2, UNISA) [ps]

P. Penna and C. Ventre.
When is cost-sharing possible?
Technical Report, 2004.
(WP2, UNISA)

Q. C. Pham.
 Etude d'un problème algorithmique intervenant dans la reconfiguration des réseaux WDM.
 Rapport de stage de Magistère d'Informatique, ENS Paris, 2004.
(WP4, UNSA/CNRS)

 L. Samper.
A markovian approach of the hidden terminal problem in ieee 802.11.
Technical Report, 2004.
(WP1, UNSA/CNRS)

 J. Serror.
Réseaux d'interconnexion : tolérance aux pannes.
Technical Report, 2004.
(WP1, UNSA/CNRS)

C. Tadonki and J. Rolim.
An integer programming heuristic for the dual powermanagement problem in wireless sensor networks.
In Proc. of the 2nd International Workshop on Managing Ubiquitous Communications and Services, (MUCS '04), 2004.
(WP1, WP5, GENEVA)

Q. Lu and H. Zhang.
Implementation of Approximation Algorithms for the Multicast Congestion Problem.
In Proc. of the 3rd International Workshop on Efficient and Experimental Algorithms (WEA '05), LNCS, Springer, 2005, to appear.
(WP4, WP5, CAU)

D. Ye and H. Zhang.
The Range Assignment Problem in Static Ad-Hoc Networks on Metric Spaces.
In Proc. of the 11th Colloquium on Structural Information and Communication Complexity (SIROCCO '04), LNCS 3104, Springer, pp. 291-302, 2004.
(WP1, CAU)

D. Ye and G. Zhang.
On-line scheduling of parallel jobs.
In Proc. of the 11th Colloquium on Structural Information and Communication Complexity (SIROCCO '04), LNCS 3104, Springer, pp. 279-290, 2004.
(WP3, CAU)

H. Zhang.
Packing: Scheduling, Embedding and Approximating Metrics.
In Proc. of the 2004 International Conference on Computational Science and its Applications (ICCSA '04), LNCS 3045, Springer, pp. 764-775, 2004.
(WP3, CAU)

H. Zhang.
Solving Packing Problem with Weaker Block Solvers.
In Proc. of the 3rd IFIP International Conference on Theoretical Computer Science (TCS '04), Kluwer Academic Publisher, pp. 293-306, 2004.
(WP3, CAU)