LAMSADE
Bazgan Cristina
Full Professor
Publications
Articles
Bazgan C., BEAUJEAN P., Gourdin É. (2022), An approximation algorithm for the maximum spectral subgraph problem, Journal of Combinatorial Optimization, vol. 44, n°3, p. 1880–1899 
Herzel A., Bazgan C., Ruzika S., Thielen C., Vanderpooten D. (2021), One-exact approximate Pareto sets, Journal of Global Optimization, vol. 80, p. 87–115
Bazgan C., Cazals P., Chlebíková J. (2021), Degree-anonymization using edge rotations, Theoretical Computer Science, vol. 873, p. 1-15
Bazgan C., Chlebíková J., Dallard C. (2020), Graphs without a partition into two proportionally dense subgraphs, Information Processing Letters, vol. 155, p. 105877
Bazgan C., Brankovic L., Casel K., Fernau H. (2020), Domination chain: Characterisation, classical complexity, parameterised complexity and approximability, Discrete Applied Mathematics, vol. 280, p. 23-42
Bazgan C., Pontoizeau T., Tuza Z. (2019), Finding a potential community in networks, Theoretical Computer Science, vol. 769, p. 32-42
Bazgan C., Chlebíková J., Dallard C., Pontoizeau T. (2019), Proportionally dense subgraph of maximum size: Complexity and approximation, Discrete Applied Mathematics, vol. 270, p. 25-36
Bazgan C., Foucaud F., Sikora F. (2019), Parameterized and approximation complexity of Partial VC Dimension, Theoretical Computer Science, vol. 766, p. 1-15
Bazgan C., Fernau H., Tuza Z. (2019), Aspects of upper defensive alliances, Discrete Applied Mathematics, vol. 266, p. 111-120
Bazgan C., Fluschnik T., Nichterlein A., Niedermeier R., Stahlberg M. (2019), A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths, Networks, vol. 73, n°1, p. 23-37
Bazgan C., Chlebikova J., Pontoizeau T. (2018), Structural and algorithmic properties of 2-community structures, Algorithmica, vol. 80, n°6, p. 180-1908
Abu-Khzam F., Bazgan C., Casel K., Fernau H. (2018), Clustering with Lower-Bounded Sizes - A General Graph-Theoretic Framework, Algorithmica, vol. 80, n°9, p. 2517-2550
Bazgan C., Brankovic L., Casel K., Fernau H., Jansen K., Klein K-M., Lampis M., Liedloff M., Monnot J., Paschos V. (2018), The many facets of upper domination, Theoretical Computer Science, vol. 717, p. 2-25
Bazgan C., Jamain F., Vanderpooten D. (2017), Discrete representation of the non-dominated set for multi-objective optimization problems using kernels, European Journal of Operational Research, vol. 260, n°3, p. 814-827
Abu-Khzam F., Bazgan C., Chopin M., Fernau H. (2016), Data Reductions and Combinatorial Bounds for Improved Approximation Algorithms, Journal of Computer and System Sciences, vol. 82, n°3, p. 503-520
Bazgan C., Bredereck R., Hartung S., Nichterlein A., Woeginger G. (2016), Finding large degree-anonymous subgraphs is hard, Theoretical Computer Science, vol. 622, p. 90-110
Bazgan C., Jamain F., Vanderpooten D. (2015), Approximate Pareto sets of minimal size for multi-objective optimization problems, Operations Research Letters, vol. 43, n°1, p. 1-6
Bazgan C., Bentz C., Picouleau C., Ries B. (2015), Blockers for the stability number and the chromatic number, Graphs and Combinatorics, vol. 31, n°1, p. 73-90
Bazgan C., Chopin M. (2014), The Complexity of Finding Harmless Individuals in Social Networks, Discrete Optimization, vol. 14, p. 170-182
Bazgan C., Chopin M., Cygan M., Fellows M., Fomin F., van Leeuwen E. (2014), Parameterized Complexity of Firefighting, Journal of Computer and System Sciences, vol. 80, n°7, p. 1285-1297
Chopin M., Nichterlein A., Bazgan C., Sikora F. (2014), Parameterized approximability of maximizing the spread of influence in networks, Journal of Discrete Algorithms, vol. 27, p. 54-65
Bazgan C., Chopin M., Nichterlein A., Sikora F. (2014), Parameterized Inapproximability of Target Set Selection and Generalizations, Computability. The Journal of the Association CiE, vol. 3, n°2, p. 135-145
Angelelli E., Bazgan C., Speranza M., Tuza Z. (2014), Complexity and approximation for Traveling Salesman Problems with profits, Theoretical Computer Science, vol. 531, p. 54-65
Bazgan C., Gourvès L., Monnot J., Pascual F. (2013), Single approximation for biobjective Max TSP, Theoretical Computer Science, vol. 478, p. 41-50
Bazgan C., Gourvès L., Monnot J. (2013), Approximation with a fixed number of solutions of some multiobjective maximization problems, Journal of Discrete Algorithms, vol. 22, p. 19-29
Bazgan C., Chopin M., Ries B. (2013), The firefighter problem with more than one firefighter on trees, Discrete Applied Mathematics, vol. 161, n°7-8, p. 899-908
Bazgan C., Toubaline S., Vanderpooten D. (2013), Critical edges for the assignment problem : complexity and exact resolution, Operations Research Letters, vol. 41, n°6, p. 685-689
Bazgan C., Jamain F., Vanderpooten D. (2013), On the number of non-dominated points of a multicriteria optimization problem, Discrete Applied Mathematics, vol. 161, n°18, p. 2841-2850
Bazgan C., Toubaline S., Vanderpooten D. (2013), Critical edges/nodes for the minimum spanning tree problem: complexity and approximation, Journal of Combinatorial Optimization, vol. 26, n°1, p. 178-189
Bazgan C., Toubaline S., Vanderpooten D. (2013), Complexity of determining the most vital elements for the p-median and p-center location problems, Journal of Combinatorial Optimization, vol. 25, n°2, p. 191-207
Bazgan C., Toubaline S., Vanderpooten D. (2012), Efficient determination of the k most vital edges for the minimum spanning tree problem, Computers and Operations Research, vol. 39, n°11, p. 2888-2898
Bazgan C., Couëtoux B., Tuza Z. (2011), Complexity and approximation of the constrained forest problem, Theoretical Computer Science, vol. 412, n°32, p. 4081-4091
Bazgan C., Toubaline S., Tuza Z. (2011), The most vital nodes with respect to independent set and vertex cover, Discrete Applied Mathematics, vol. 159, n°17, p. 1933-1946
Aissi H., Bazgan C., Vanderpooten D. (2010), General approximation schemes for min–max (regret) versions of some (pseudo-)polynomial problems, Discrete Optimization, vol. 7, n°3, p. 136-148
Bazgan C., Tuza Z., Vanderpooten D. (2010), Satisfactory graph partition, variants, and generalizations, European Journal of Operational Research, vol. 206, n°2, p. 271-280
Aissi H., Bazgan C., Vanderpooten D. (2009), Min–max and min–max regret versions of combinatorial optimization problems: A survey, European Journal of Operational Research, vol. 197, n°2, p. 427-438
Bazgan C., Hugot H., Vanderpooten D. (2009), Implementing an efficient fptas for the 0–1 multi-objective knapsack problem, European Journal of Operational Research, vol. 198, n°1, p. 47-56
Bazgan C., Hugot H., Vanderpooten D. (2009), Solving efficiently the 0-1 multi-objective knapsack problem, Computers and Operations Research, vol. 36, n°1, p. 260-279
Aissi H., Bazgan C., Vanderpooten D. (2008), Complexity of the min-max (regret) versions of cut problems, Discrete Optimization, vol. 5, n°1, p. 66-73
Bazgan C., Tuza Z., Vanderpooten D. (2008), Approximation of satisfactory bisection problems, Journal of Computer and System Sciences, vol. 74, n°5, p. 875-883
Bazgan C., Tuza Z. (2008), Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3, Journal of Discrete Algorithms, vol. 6, n°3, p. 510-519
Bazgan C., Tuza Z., Vanderpooten D. (2007), Efficient algorithms for decomposing graphs under degree constraints, Discrete Applied Mathematics, vol. 155, n°8, p. 979-988
Aissi H., Bazgan C., Vanderpooten D. (2007), Approximation of min-max and min-max regret versions of some combinatorial optimization problems, European Journal of Operational Research, vol. 179, n°2, p. 281-290
Bazgan C., Tuza Z., Vanderpooten D. (2006), The satisfactory partition problem, Discrete Applied Mathematics, vol. 154, n°8, p. 1236-1245
Bazgan C., Tuza Z., Vanderpooten D. (2006), Degree-constrained decompositions of graphs: bounded treewidth and planarity, Theoretical Computer Science, vol. 355, n°3, p. 389-395
Bazgan C., Monnot J., Paschos V., Serrière F. (2005), On the differential approximation of MIN SET COVER, Theoretical Computer Science, vol. 332, n°1-3, p. 497-513
Aissi H., Bazgan C., Vanderpooten D. (2005), Complexity of the min-max and min-max regret assignment problems, Operations Research Letters, vol. 33, n°6, p. 634-640
Ausiello G., Bazgan C., Demange M., Paschos V. (2005), Completeness in differential approximation classes, International Journal of Foundations of Computer Science, vol. 16, n°6, p. 1267-1295
Bazgan C., Escoffier B., Paschos V. (2005), Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness, Theoretical Computer Science, vol. 339, n°2-3, p. 272-292
Bazgan C., Monnot J., Hassin R. (2005), Approximation algorithms for some vehicle routing problems, Discrete Applied Mathematics, vol. 146, n°1, p. 27-42
Bazgan C. (2004), A note on the approximability of the toughness of graphs, Discrete Mathematics, vol. 280, n°1-3, p. 215-218
Bazgan C., Paschos V. (2003), Differential approximation for satisfiability and related problems, European Journal of Operational Research, vol. 147, n°2, p. 397-404
Bazgan C., Fernandez de la Vega W., Karpinski M. (2003), Polynomial time approximation schemes for dense instances of minimum constraint satisfaction, Random Structures & Algorithms, vol. 23, n°1, p. 73-91
Ouvrages
Bazgan C., Fernau H. (2022), Combinatorial Algorithms, Berlin Heidelberg: Springer International Publishing, 524 p.
Chapitres d'ouvrage
Bazgan C. (2010), Optimal Satisfiability, in Paschos, Vangelis Th., Paradigms of Combinatorial Optimization: Problems and New Approaches Wiley, p. 704
Bazgan C. (2007), Complexité des problèmes de satisfaction de contraintes booléennes, in Paschos, Vangelis Th., Optimisation combinatoire 5 : problèmes paradigmatiques et nouvelles problematiques, Paris: Lavoisier, p. 21-50
Communications avec actes
Bazgan C., Casel K., Cazals P. (2022), Dense Graph Partitioning on Sparse and Dense Graphs, in , Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Dang C., Bazgan C., Cazenave T., Chopin M., Wuillemin P-H. (2022), Monte Carlo Search Algorithms for Network Traffic Engineering, in , Société Française de Recherche Opérationnelle et d’Aide à la Décision (ROADEF)
Abu-Khzam F., Bazgan C., Fernau H. (2020), Parameterized Dynamic Variants of Red-Blue Dominating Set, in Chatzigeorgiou, Alexander; Dondi, Riccardo; Herodotou, Herodotos, Springer, 236-247 p.
Bazgan C., Cazals P., Chlebíková J. (2020), How to Get a Degree-Anonymous Graph Using Minimum Number of Edge Rotations, in Wu, Weili; Zhang, Zhongnan, Berlin Heidelberg, Springer, 242-256 p.
Bazgan C., Herzel A., Ruzika S., Thielen C., Vanderpooten D. (2019), An FPTAS for a General Class of Parametric Optimization Problems, in Ding-Zhu Du, Zhenhua Duan, Cong Tian, 25th International Conference on Computing and Combinatorics (COCOON 19), Springer, 25-37 p.
Bazgan C., Herzel A., Ruzika S., Thielen C., Vanderpooten D. (2019), An FPTAS for a General Class of Parametric Optimization Problems, in Ding-Zhu Du, Zhenhua Duan, Cong Tian, 25th International Conference, COCOON 2019, Springer, 25-37 p.
Bazgan C., Beaujean P., Gourdin E. (2018), Relaxation and Matrix Randomized Rounding for the Maximum Spectral Subgraph Problem, in Donghyun Kim, R. N. Uma, Alexander Zelikovsky, 12th International Conference on Combinatorial Optimization and Applications (COCOA 18), Springer, 108-122 p.
Bazgan C., Pontoizeau T., Tuza Z. (2017), On the complexity of finding a potential community, in Fotakis Dimitris, Pagourtzis Aris, Paschos Vangelis Th., Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC 2017), Springer, 80-91 p.
Bazgan C., Brankovic L., Casel K., Fernau H., Jansen K., Klein K-M., Lampis M., Liedloff M., Monnot J., Paschos V. (2016), Upper Domination : Complexity and Approximation, in Veli Mäkinen, Simon J. Puglisi, Leena Salmela, Combinatorial Algorithms. 27th International Workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016, Proceedings, Berlin Heidelberg, Springer, 241-252 p.
Bazgan C., Brankovic L., Casel K., Fernau H., Jansen K., Klein K-M., Lampis M., Liedloff M., Monnot J., Paschos V. (2016), Algorithmic Aspects of Upper Domination: A Parameterized Perspective, in Riccardo Dondi, Guillaume Fertin, Giancarlo Mauri, Algorithmic Aspects in Information and Management. 11th International Conference, AAIM 2016, Bergamo, Italy, July 18-20, 2016, Proceedings, Berlin Heidelberg, Springer, 113-124 p.
Bazgan C., Brankovic L., Casel K., Fernau H. (2016), On the Complexity Landscape of the Domination Chain, in Sathish Govindarajan, Anil Maheshwari, Algorithms and Discrete Applied Mathematics - Second International Conference, CALDAM 2016, Berlin Heidelberg, Springer, 61-72 p.
Abu-Khzam F., Bazgan C., Casel K., Fernau H. (2016), Building Clusters with Lower-Bounded Sizes, in Seok-Hee Hong, 27th International Symposium on Algorithms and Computation, ISAAC 2016, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 148:1–148:12 p.
Bazgan C., Foucaud F., Sikora F. (2016), On the Approximability of Partial VC Dimension, in T-H. Hubert Chan, Minming Li, Lusheng Wang, Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Berlin Heidelberg, Springer, 92-106 p.
Bazgan C., Chlebikova J., Pontoizeau T. (2015), New Insight into 2-Community Structures in Graphs with Applications in Social Networks, in Zaixin Lu, Donghyun Kim, Weili Wu, Wei Li, Ding-Zhu Du, Combinatorial Optimization and Applications - 9th International Conference, COCOA 2015, Berlin Heidelberg, Springer, 236-250 p.
Bazgan C., Nichterlein A., Niedermeier R. (2015), A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths, in Vangelis Th. Paschos, Peter Widmayer, Algorithms and Complexity - 9th International Conference, CIAC 2015, Berlin Heidelberg, Springer, 47-60 p.
Abu-Khzam F., Bazgan C., El Haddad J., Sikora F. (2015), On the Complexity of QoS-Aware Service Selection Problem, in Alistair Barros, Daniela Grigori, Nanjangud C. Narendra, Hoa Khanh Dam, Service-Oriented Computing. 13th International Conference, ICSOC 2015, Goa, India, November 16-19, 2015, Proceedings, Springer, 345-352 p.
Abu-Khzam F., Bazgan C., Chopin M., Fernau H. (2014), Approximation Algorithms Inspired by Kernelization Methods, in Hee-Kap Ahn, Chan-Su Shin, Algorithms and Computation - 25th International Symposium, ISAAC 2014, Springer, 479-490 p.
Bazgan C., Nichterlein A. (2014), Parameterized Inapproximability of Degree Anonymization, in Marek Cygan, Pinar Heggernes, Parameterized and Exact Computation - 9th International Symposium, IPEC 2014, Berlin Heidelberg, Springer, 75-84 p.
Bazgan C., Chopin M., Nichterlein A., Sikora F. (2014), Parameterized Inapproximability of Target Set Selection and Generalizations, in Arnold Beckmann, Erzsébet Csuhaj-Varjú, Klaus Meer, Language, Life, Limits.10th Conference on Computability in Europe, CiE 2014, Budapest, Hungary, June 23-27, 2014. Proceedings, Berlin Heidelberg, Springer, 11-20 p.
Bazgan C., Chopin M., Nichterlein A., Sikora F. (2013), Parameterized Approximability of Maximizing the Spread of Influence in Networks, in Ding-Zhu Du, Guochuan Zhang, Computing and Combinatorics. 19th International Conference, COCOON 2013, Hangzhou, China, June 21-23, 2013. Proceedings, Berlin Heidelberg, Springer, 543-554 p.
Bazgan C., Gourvès L., Monnot J. (2012), Approximation with a Fixed Number of Solutions of Some Biobjective Maximization Problems, in Solis-Oba, Roberto, WAOA 2011, Saarbrücken, Springer, 233-246 p.
Bazgan C., Gourvès L., Monnot J., Pascual F. (2012), Single Approximation for Biobjective Max TSP, in Solis-Oba, Roberto, WAOA 2011, Saarbrücken, Springer, 49-62 p.
Bazgan C., Chopin M. (2012), The Robust Set Problem: Parameterized Complexity and Approximation, in Widmayer, Peter, Mathematical Foundations of Computer Science 2012 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012, Proceedings, Bratislava, Springer, 136-147 p.
Bazgan C., Toubaline S., Tuza Z. (2011), Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures, in Smyth, William F., Combinatorial Algorithms 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers, Londres, Springer, 154-166 p.
Bazgan C., Chopin M., Fellows M. (2011), Parameterized Complexity of the Firefighter Problem, in Watanabe, Osamu, ISAAC 2011, Yokohama, Springer, 643-652 p.
Bazgan C., Toubaline S., Vanderpooten D. (2011), Efficient Algorithms for Finding the k Most Vital Edges for the Minimum Spanning Tree Problem, in Zhu, Xuding, Combinatorial Optimization and Applications 5th International Conference, COCOA 2011, Zhangjiajie, Springer, 126-140 p.
Bazgan C., Couëtoux B., Tuza Z. (2009), Covering a Graph with a Constrained Forest, in Yingfei Dong, Ding-Zhu Du, Oscar Ibarra, Algorithms and Computation 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings, Honolulu, Springer, 892-901 p.
Bazgan C., Hugot H., Vanderpooten D. (2007), An efficient implementation for the 0-1 multi-objective knapsack problem, in Demetrescu, Camil, Experimental Algorithms 6th International Workshop, WEA 2007, Rome, Italy, June 6-8, 2007, Proceedings, Rome, Springer, 406-419 p.
Bazgan C., Hugot H., Vanderpooten D. (2007), A practical efficient fptas for the 0-1 multi-objective knapsack problem, in Welzl, Emo, Algorithms - ESA 2007 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, Proceedings, Eilat, Springer, 717-728 p.
Aissi H., Bazgan C., Vanderpooten D. (2006), Approximating min-max (regret) versions of some polynomial problems, in Lee, D.T., Computing and Combinatorics 12th Annual International Conference, COCOON 2006, Taipei, Taiwan, August 15-18, 2006, Proceedings, Taipei, Springer, 428-438 p.
Bazgan C., Monnot J., Paschos V., Serrière F. (2005), Greedy differential approximations for MIN SET COVER, in Vojtas, Peter, SOFSEM'05 : Theory and Practice of Computer Science, Liptovský Ján, Springer, 62-71 p.
Bazgan C., Tuza Z., Vanderpooten D. (2005), Complexity and approximation of satisfactory partition problems, in Wang, Lusheng, Computing and Combinatorics 11th Annual International Conference, COCOON 2005, Kunming, China, August 16-19, 2005, Proceedings, Kunming, Springer, 829-838 p.
Aissi H., Bazgan C., Vanderpooten D. (2005), Pseudo-polynomial algorithms for min-max and min-max regret problems, in Xian-Sun, Zhang, Operations Research and Its Applications. The Fifth International Symposium, ISORA’05 Tibet, China, August 8–13, 2005 Proceedings, Lhassa, World Publishing Corporation, 171-178 p.
Aissi H., Bazgan C., Vanderpooten D. (2005), Complexity of the min-max (regret) versions of cut problems, in Du, Ding-Zhu, Algorithms and Computation 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005, Proceedings, Sanya (Hainan), Springer, 789-798 p.
Aissi H., Bazgan C., Vanderpooten D. (2005), Approximation complexity of min-max (regret) versions of shortest path, spanning tree, and knapsack, in Leonardi, Stefano, Algorithms – ESA 2005 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005, Proceedings, Palma de Mallorca, Springer, 862-873 p.
Bazgan C., Escoffier B., Paschos V. (2004), Poly-APX- and PTAS-completeness in standard and differential approximation, in Trippen, Gerhard, ISAAC'04 :15th International Symposium, Hong Kong, Springer, 124-136 p.
Bazgan C., Tuza Z., Vanderpooten D. (2003), On the existence and determination of satisfactory partitions in a graph, in Ono, Hirotaka, Algorithms and Computation 14th International Symposium, ISAAC 2003, Kyoto, Japan, December 15-17, 2003, Proceedings, Kyoto, Springer, 444-453 p.
Ausiello G., Bazgan C., Demange M., Paschos V. (2003), Completeness in differential approximation classes, in Vojtas, Peter, Mathematical Foundations of Computer Science 2003 28th International Symposium, MFCS 2003, Bratislava, Slovakia, August 25-29, 2003, Proceedings, Bratislava, Springer, 179-188 p.
Bazgan C., Hassin R., Monnot J. (2003), Differential approximation for some routing problems, in Silvestri, Riccardo, Algorithms and Complexity 5th Italian Conference, CIAC 2003, Rome, Italy, May 28-30, 2003, Proceedings, Rome, Springer, 277-288 p.
Bazgan C., Fernandez de la Vega W., Karpinski M. (2002), Approximability of Dense Instances of NEAREST CODEWORD Problem, in Martti Penttonen, Erik Meineche Schmidt, Algorithm Theory — SWAT 2002 8th Scandinavian Workshop on Algorithm Theory Turku, Finland, July 3–5, 2002 Proceedings, Berlin Heidelberg, Springer, 298-307 p.
Communications sans actes
Jamain F., Bazgan C., Vanderpooten D. (2014), Approximation in multiobjective optimization using e-kernels, 15ème congrès annuel de la Société française de recherche opérationnelle et d’aide à la décision (ROADEF'14), Bordeaux, France
Jamain F., Bazgan C., Vanderpooten D. (2013), On Approximate Kernels of Minimal Size for Bicriteria Problems, 22nd International Conference on Multiple Criteria Decision Making (MCDM’13), 2013, Malaga, Espagne
Jamain F., Bazgan C., Vanderpooten D. (2013), Approximation de taille minimale de l'ensemble de Pareto de problèmes multicritères, 14ème congrès annuel de la Société française de recherche opérationnelle et d’aide à la décision (ROADEF'13), Troyes, France
Bazgan C., Escoffier B., Gourvès L., Monnot J., Pascual F., Vanderpooten D. (2012), Solutions équitables approchées pour divers problèmes d’optimisation combinatoire, 13ème congrès annuel de la Société française de recherche opérationnelle et d’aide à la décision (ROADEF'12), Angers, France
Jamain F., Bazgan C., Vanderpooten D. (2012), Sur le nombre de points non dominés d'un problème multicritères, 13ème congrès annuel de la Société française de recherche opérationnelle et d’aide à la décision (ROADEF'12), Angers, France
Prépublications / Cahiers de recherche
Bazgan C., Tuza Z., Vanderpooten D. (2003), Complexity of the satisfactory partition problem, Note de recherche du LAMSADE, 13 p.
Bazgan C., Tuza Z., Vanderpooten D. (2003), Decomposition of graphs: some polynomial cases, Note de recherche du LAMSADE, 11 p.