Publications of Ignasi Sau

BACK TO COATI PUBLICATION INDEX

Publications of Ignasi Sau

Thesis
  1. I. Sau. Optimization in Graphs under Degree Constraints. Application to Telecommunication Networks. PhD thesis, Université de Nice-Sophia Antipolis (UNS) and Universitat Politècnica de Catalunya (UPC), October 2009. [PDF ]
    Keywords: Graph theory, traffic grooming, optical networks, graph partitioning, computational complexity, approximation algorithms, parameterized complexity, branchwidth, dynamic programming, graphs on surfaces. [Abstract] [bibtex-entry]
     
Articles in journal or book's chapters
  1. Nathann Cohen, Frédéric Havet, Dorian Mazauric, Ignasi Sau, and Rémi Watrigant. Complexity dichotomies for the Minimum F -Overlay problem. Journal of Discrete Algorithms, 52-53:133-142, September 2018. [WWW ] [PDF ] [bibtex-entry]
     
  2. O. Amini, D. Peleg, S. Pérennes, I. Sau, and S. Saurabh. On the approximability of some degree-constrained subgraph problems. Discrete Applied Mathematics, 160(12):1661 - 1679, 2012. [WWW ] [PDF ] [Abstract] [bibtex-entry]
     
  3. J-C. Bermond, D. Coudert, J. Moulierac, S. Pérennes, I. Sau, and F. Solano Donado. GMPLS Label Space Minimization through Hypergraph Layouts. Theoretical Computer Science (TCS), 444:3-16, July 2012. [WWW ] [PDF ] [Abstract] [bibtex-entry]
     
  4. J-C. Bermond, X. Muñoz, and I. Sau. Traffic Grooming in Bidirectional WDM Ring Networks. Networks, 58(1):20-35, 2011. [WWW ] [PDF ] [Abstract] [bibtex-entry]
     
  5. D. Coudert, F. Giroire, and I. Sau. Circuits in graphs through a prescribed set of ordered vertices. Journal of Interconnection Networks (JOIN), 11(3-4):121-141, 2011. [WWW ] [PDF ] [Abstract] [bibtex-entry]
     
  6. J-C. Bermond, C. J. Colbourn, L. Gionfriddo, G. Quattrocchi, and I. Sau. Drop Cost and Wavelength Optimal Two-Period Grooming with Ratio 4. SIAM Journal on Discrete Mathematics, 24(2):400-419, 2010. [PDF ] [Abstract] [bibtex-entry]
     
  7. T. Cinkler, D. Coudert, M. Flammini, G. Monaco, L. Moscardelli, X. Muñoz, I. Sau, M. Shalom, and S. Zaks. Graphs and Algorithms in Communication Networks: Studies in Broadband, Optical, Wireless, and Ad Hoc Networks, volume XXVII of EATCS Texts in Theoretical Computer Science, chapter Traffic Grooming: Combinatorial Results and Practical Resolutions, pages 63-94. Springer, A. Koster and X. Muñoz edition, 2010. [WWW ] [PDF ] [Abstract] [bibtex-entry]
     
  8. I. Sau and D. M. Thilikos. Subexponential Parameterized Algorithms for Degree-constrained Subgraph Problems on Planar Graphs. Journal of Discrete Algorithms, 8(3):330-338, September 2010. [WWW ] [PDF ] [Abstract] [bibtex-entry]
     
  9. O. Amini, S. Pérennes, and I. Sau. Hardness and Approximation of Traffic Grooming. Theoretical Computer Science, 410(38-40):3751-3760, 2009. [PDF ] [Abstract] [bibtex-entry]
     
  10. F. Huc, I. Sau, and J. Zerovnik. $(\ell,k)$-Routing on Plane Grids. Journal of Interconnection Networks, 10(1-2):27-57, 2009. [PDF ] [Abstract] [bibtex-entry]
     
  11. G. B. Mertzios, I. Sau, and S. Zaks. A New Intersection Model and Improved Algorithms for Tolerance Graphs. SIAM Journal on Discrete Mathematics, 23:1800-1813, 2009. [WWW ] [PDF ] [Abstract] [bibtex-entry]
     
  12. I. Sau and J. Zerovnik. Graphs and Algorithms in Communication Networks: Studies in Broadband, Optical, Wireless, and Ad Hoc Networks, volume XXVII of EATCS Texts in Theoretical Computer Science, chapter Permutation Routing and $(\ell,k)$-Routing on Plane Grids, pages 265-279. Springer, A. Koster and X. Muñoz edition, November 2009. [WWW ] [PDF ] [Abstract] [bibtex-entry]
     
  13. I. Sau and J. Zerovnik. An Optimal Permutation Routing Algorithm on Full-Duplex Hexagonal Networks. Discrete Mathematics and Theoretical Computer Science, 10(3):49-62, 2008. [PDF ] [Abstract] [bibtex-entry]
     
Conference's articles
  1. Nathann Cohen, Frédéric Havet, Dorian Mazauric, Ignasi Sau, and Rémi Watrigant. Complexity Dichotomies for the Minimum $F$-Overlay Problem. In IWOCA: International Workshop on Combinatorial Algorithms, Newcastle, Australia, pages 12, July 2017. [WWW ] [PDF ]
    Keywords: Fixed-parameter tractability, Hypergraph, Minimum F-Overlay Problem, NP-completeness. [bibtex-entry]
     
  2. J. Araujo, C. Linhares Sales, and I. Sau. Weighted Coloring on $P_4$-sparse Graphs. In 11es Journées Doctorales en Informatique et Réseaux (JDIR 2010), Sophia Antipolis, France, pages 33--38, March 2010. [PDF ] [Abstract] [bibtex-entry]
     
  3. G. B. Mertzios, I. Sau, and S. Zaks. The Recognition of Tolerance and Bounded Tolerance Graphs. In Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 5 of LIPIcs, pages 585-596, 2010. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. [WWW ] [PDF ] [Abstract] [bibtex-entry]
     
  4. J-C. Bermond, D. Coudert, J. Moulierac, S. Perennes, H. Rivano, I. Sau, and F. Solano Donado. MPLS label stacking on the line network. In L. Fratta et al., editor, IFIP Networking, volume 5550 of Lecture Notes in Computer Science, Aachen, Germany, pages 809-820, May 2009. Springer. [WWW ] [PDF ] [Abstract] [bibtex-entry]
     
  5. J-C. Bermond, D. Coudert, J. Moulierac, S. Perennes, I. Sau, and F. Solano Donado. Designing Hypergraph Layouts to GMPLS Routing Strategies. In 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO), volume 5869 of Lecture Notes in Computer Science, Piran, Slovenia, pages 57--71, May 2009. Springer. [WWW ] [PDF ] [Abstract] [bibtex-entry]
     
  6. D. Coudert, F. Giroire, and I. Sau. Edge-Simple Circuits Through 10 Ordered Vertices in Square Grids. In J. Kratochvìl and M. Miller, editors, 20th International Workshop on Combinatorial Algorithms -- IWOCA, volume 5874 of Lecture Notes in Computer Science, Hradec nad Moravicì, Czech Republic, pages 134-145, June 2009. Springer. [WWW ] [PDF ] [Abstract] [bibtex-entry]
     
  7. Z. Li and I. Sau. Graph Partitioning and Traffic Grooming with Bounded Degree Request Graph. In 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009), volume 5911 of Lecture Notes in Computer Science, pages 250-261,, June 2009.
    Note: Best student paper award. [PDF ] [Abstract] [bibtex-entry]
     
  8. G. Mertzios, I. Sau, and S. Zaks. A New Intersection Model and Improved Algorithms for Tolerance Graphs. In 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009), volume 5911 of Lecture Notes in Computer Science, pages 285-295, 06 2009. [PDF ] [Abstract] [bibtex-entry]
     
  9. I. Sau and D. M. Thilikos. Subexponential Parameterized Algorithms for Bounded-Degree Connected Subgraph Problems on Planar Graphs. In DIMAP workshop on Algorithmic Graph Theory (AGT09), volume 32 of Electronic Notes in Discrete Mathematics, Warwick, UK, pages 59-66, March 2009. Elsevier. [PDF ] [Abstract] [bibtex-entry]
     
  10. I. Sau and D. M. Thilikos. On Self-Duality of Branchwidth in Graphs of Bounded Genus. In 8th Cologne Twente Workshop on Graphs and Combinatorial Optimization (CTW), Paris, France, pages 19-22, June 2009. [PDF ] [Abstract] [bibtex-entry]
     
  11. O. Amini, D. Peleg, S. Pérennes, I. Sau, and S. Saurabh. Degree-Constrained Subgraph Problems : Hardness and Approximation Results. In 6th International Workshop on Approximation and Online Algorithms (ALGO-WAOA 2008), volume 5426 of Lecture Notes in Computer Science, Karlsruhe, Germany, pages 29-42, September 2008. [PDF ] [Abstract] [bibtex-entry]
     
  12. O. Amini, I. Sau, and S. Saurabh. Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem. In The International Workshop on Parameterized and Exact Computation (IWPEC 2008), volume 5008 of Lecture Notes in Computer Science, Victoria, Canada, pages 13-29, May 2008. [PDF ] [Abstract] [bibtex-entry]
     
  13. X. Muñoz and I. Sau. Traffic Grooming in Unidirectional WDM Rings with Bounded-Degree Request Graph. In 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2008), volume 5344 of Lecture Notes in Computer Science, pages 300-311, June 2008. [PDF ] [Abstract] [bibtex-entry]
     
  14. O. Amini, S. Pérennes, and I. Sau. Hardness and Approximation of Traffic Grooming. In The 18th International Symposium on Algorithms and Computation (ISAAC 2007), volume 4835 of Lecture Notes in Computer Science, Sendai, Japan, pages 561-573, December 2007. Springer-Verlag. [WWW ] [PDF ] [Abstract] [bibtex-entry]
     
  15. O. Amini, S. Pérennes, and I. Sau. Hardness of Approximating the Traffic Grooming. In Neuvièmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'07), Ile d'Oléron, France, pages 45-48, May 2007. [WWW ] [PDF ] [Abstract] [bibtex-entry]
     
  16. I. Sau and J. Zerovnik. Optimal Permutation Routing on Mesh Networks. In Proc. of International Network Optimization Conference (INOC 2007), Spa, Belgium, pages 6p, April 2007. [PDF ] [Abstract] [bibtex-entry]
     
  17. J-C. Bermond, D. Coudert, X. Muñoz, and I. Sau. Traffic Grooming in Bidirectional WDM ring networks. In IEEE-LEOS ICTON / COST 293 GRAAL, volume 3, pages 19-22, June 2006. [PDF ] [Abstract] [bibtex-entry]
     
Internal reports
  1. J-C. Bermond, C.J. Colbourn, L. Gionfriddo, G. Quattrocchi, and I. Sau. Drop cost and wavelength optimal two-period grooming with ratio 4. Technical report RR-7101, INRIA, November 2009. [PDF ] [Abstract] [bibtex-entry]
     
  2. J-C. Bermond, D. Coudert, J. Moulierac, S. Perennes, H. Rivano, I. Sau, and F. Solano Donado. MPLS label stacking on the line network. Technical report RR-6803, INRIA, January 2009. [WWW ] [PDF ] [Abstract] [bibtex-entry]
     
  3. J-C. Bermond, D. Coudert, J. Moulierac, S. Perennes, I. Sau, and F. Solano Donado. GMPLS Label Space Minimization through Hypergraph Layouts. Research Report RR-7071, INRIA, October 2009. [WWW ] [PDF ]
    Keywords: GMPLS, optical networks, label stacking, hypergraph layout, approximation algorithms, dynamic programming.. [Abstract] [bibtex-entry]
     
  4. J-C. Bermond, D. Coudert, J. Moulierac, S. Perennes, I. Sau, and F. Solano Donado. GMPLS Routing Strategies based on the Design of Hypergraph Layouts. Technical report RR-6842, INRIA, February 2009. [WWW ] [PDF ] [Abstract] [bibtex-entry]
     
  5. J-C. Bermond, X. Muñoz, and I. Sau. Traffic Grooming in Bidirectional WDM Ring Networks. Technical report RR-7080, INRIA, October 2009. [WWW ] [PDF ] [Abstract] [bibtex-entry]
     
  6. D. Coudert, F. Giroire, and I. Sau. Circuit visiting 10 ordered vertices in infinite grids. Technical report RR-6910, INRIA, 2009. [WWW ] [PDF ] [Abstract] [bibtex-entry]
     
  7. J. Rué, I. Sau, and D. M. Thilikos. Dynamic Programming for Graphs on Surfaces. Technical report RR-7166, INRIA, December 2009. [PDF ] [Abstract] [bibtex-entry]
     
  8. O. Amini, F. Huc, I. Sau, and J. Zerovnik. $(\ell,k)$-Routing on Plane Grids. Research Report 6480, INRIA, March 2008. [WWW ] [PDF ] [Abstract] [bibtex-entry]
     
  9. O. Amini, D. Peleg, S. Pérennes, I. Sau, and S. Saurabh. Degree-Constrained Subgraph Problems: Hardness and Approximation Results. Research Report RR-6690, INRIA, October 2008. [WWW ] [PDF ] [Abstract] [bibtex-entry]
     
  10. J-C. Bermond, I. Caragiannis, D. Coudert, F. Diedrich, L. Hogie, F. Huc, C. Molle, J. Monteiro, P. Leone, H. Rivano, and I. Sau. Algorithmic solutions for critical resource sharing: third year. Technical report Deliverable 2.2.3, IST FET AEOLUS, Integrated Project IST-015964, 2008. [PDF ] [bibtex-entry]
     
  11. X. Muñoz and I. Sau. Traffic Grooming in Unidirectional WDM Rings with Bounded Degree Request Graph. Research Report RR-6481, INRIA, March 2008. [WWW ] [PDF ] [Abstract] [bibtex-entry]
     
  12. S. Pérennes and I. Sau. Sur la Conjecture des Jeux Uniques. Research Report RR-6691, INRIA, October 2008. [WWW ] [PDF ] [Abstract] [bibtex-entry]
     
  13. O. Amini, S. Pérennes, and I. Sau. Hardness and Approximation of Traffic Grooming. Research Report 6236, INRIA, June 2007. [WWW ] [PDF ] [Abstract] [bibtex-entry]
     
  14. O. Amini, I. Sau, and S. Saurabh. Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem. Research Report 6237, INRIA, June 2007. [WWW ] [PDF ] [Abstract] [bibtex-entry]
     
  15. J-C. Bermond, I. Caragiannis, D. Coudert, C. Gomes, I. Guerin-Lassous, G. Huiban, C. Molle, and I. Sau. Algorithmic solutions for critical resource sharing: second year. Technical report Deliverable 2.2.2, IST FET AEOLUS, Integrated Project IST-015964, 2007. [PDF ] [bibtex-entry]
     
Miscellaneous
  1. I. Sau. Minimizing the number of ADMs in WDM Optical Rings with Traffic Grooming. Master's thesis, Université Polytechnique de Barcelone, Espagne, 2006. [bibtex-entry]
     

BACK TO COATI PUBLICATION INDEX


Last modified: Sat Jan 29 19:00:46 2022