Christophe Picouleau
Professeur des Universités
Équipe : Optimisation combinatoire
Bureau : 31.1.81
Principaux thèmes de recherche : théorie des graphes, algorithmes
2024
Articles de revue
- The Complexity of 2-Intersection Graphs of 3-Hypergraphs Recognition for Claw-free Graphs and triangulated Claw-free Graphs. In Discrete Applied Mathematics, 355: 232-246, 2024. doi www
- On the complexity of Dominating Set for graphs with fixed diameter. In Theoretical Computer Science: 114561, 2024. doi www
Non publié
- Complexity and algorithms for constant diameter augmentation problems. , working paper or preprint. doi www
2022
Articles de revue
- Complexity and algorithms for constant diameter augmentation problems. In Theoretical Computer Science, 904: 15-26, 2022. doi www
Articles de conférence
- The Perfect Matching-Cut problem in bipartite graphs with diameter three. In ICGT 2022, Montpellier, France, 2022. www
- Partition de graphe sous contrainte de ratio de degré. In 23ème congrès annuel de la Société Franc caise de Recherche Opérationnelle et d'Aide `a la Décision, Villeurbanne - Lyon, France, 2022. www
- Couplage parfait disconnectant pour les graphes bipartis de diamètre 3. In 23ème congrès annuel de la Société Franc caise de Recherche Opérationnelle et d'Aide `a la Décision, Villeurbanne - Lyon, France, 2022. www
2021
Articles de revue
- On the vertices belonging to all, some, none minimum dominating set. In Discrete Applied Mathematics, 288: 9-19, 2021. doi www
- Characterization of the degree sequences of (quasi) regular uniform hypergraphs. In Theoretical Computer Science, 868: 97-111, 2021. doi www
Non publié
- The Minimum Dominating Set problem is polynomial for (claw, P8)-free graphs. , working paper or preprint. www
2020
Articles de revue
- Minimal graphs for hamiltonian extension. In Open Journal of Discrete Applied Mathematics, 2020. doi www
- Minimal graphs for 2-factor extension. In Discrete Applied Mathematics, 2020. doi www
Non publié
- Partition of graphs with maximum degree ratio. , working paper or preprint. www
- On Minimum Dominating Sets in cubic and (claw,H)-free graphs. , working paper or preprint. www
- The complexity of the Perfect Matching-Cut problem. , working paper or preprint. www
- Adaptive network flow with $k$-Arc Destruction. , working paper or preprint. www
2019
Articles de revue
- Critical vertices and edges in H-free graphs. In Discrete Applied Mathematics, 257: 361-367, 2019. doi www
- On graceful difference labelings of disjoint unions of circuits. In Open Journal of Discrete Applied Mathematics, 2 (3): 38-55, 2019. doi www
Articles de conférence
- Impact of calibration of perturbations in simulation: the case of robustness evaluation at a station. In RailNorrk"oping 2019. 8th International Conference on Railway Operations Modelling and Analysis (ICROMA), Norrk"oping, Sweden, 2019. www
2018
Articles de revue
- Contraction and deletion blockers for perfect graphs and H-free graphs. In Theoretical Computer Science, 746: 49-72, 2018. doi www
- Minimal graphs for matching extension. In Discrete Applied Mathematics, 234: 47-55, 2018. doi www
Articles de conférence
- Estimating long-term delay risk with Generalized Linear Models. In 2018 21st International Conference on Intelligent Transportation Systems (ITSC), pages 2911-2916, IEEE, Maui, France, 2018. doi www
- Modelling passenger train arrival delays with Generalized Linear Models and its perspective for scheduling at main stations. In 8th International Conference on Railway Engineering (ICRE 2018), IET, London, United Kingdom, 2018. doi www
- Extenseurs hamiltoniens minimaux. In ROADEF, Lorient, France, 2018. www
2017
Articles de conférence
- d-extensibles de stables dans les graphes bipartis. In ROADEF2017. 18ème congrès annuel de la Société Franc caise de Recherche Opérationnelle et d'Aide `a la Décision, Metz, France, 2017. www
2015
Articles de revue
- Blockers for the stability number and the chromatic number. In Graphs and Combinatorics, 31 (1): 73-90, 2015. doi www
Articles de conférence
- Contraction Blockers for Graphs with Forbidden Induced Paths. In 9th International Conference on Algorithms and Complexity (CIAC 2015), pages 194-207, Springer, Paris, France, Algorithms and Complexity 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015. Proceedings 9079, 2015. doi www
2014
Articles de conférence
- d-extensible sets of stable sets in bipartite graphs. In GO IX, Ninth international colloquium on Graphs and Optimization, pages 14, X, France, 2014. www
- Minimum size extensible graphs for (near) perfect matchings. In International Conference on Graph Theory, pages juin 2014, Grenoble, France, 2014. www
2013
Livres
Articles de conférence
- How to decompose a binary matrix into three hv-convex polyominoes. In 17th IAPR International Conference on Discrete Geometry for Computer Imagery, pages 311-322, Séville, Spain, LNCS 7749, 2013. www
- On the degree sequences of uniform hypergraphs. In 17th IAPR International Conference on Discrete Geometry for Computer Imagery, pages 300-310, Séville, Spain, LNCS 7749, 2013. www
2012
Articles de revue
- On the NP-Completeness of the Perfect Matching Free Subgraph Problem. In Theoretical Computer Science, 423: 25-29, 2012. doi www
- Minimum decomposition into convex binary matrices. In Discrete Applied Mathematics, 160 (7-8): 1164-1175, 2012. doi www
- d-Transversals of Stable Sets and Vertex Covers in Weighted Bipartite Graphs. In Journal of Discrete Algorithms, 17: 95-102, 2012. doi www
2011
Articles de revue
- Minimum d-blockers and d-transversals in graphs. In Journal of Combinatorial Optimization, 22 (4): 857-872, 2011. doi www
Chapitres d'ouvrage
- Weighted Transversals and Blockers for Some Optimization Problems in Graphs. In Progress in Combinatorial Optimization, pages 203-222, 2011. www
Articles de conférence
- Minimum d-Transversals of Maximum-Weight Stable Sets in Trees. In European conference on combinatorics, graph theory and applications. EuroComb'11, pages 129-134, Budapest, Hungary, 2011. doi www
- Minimum Transversals for the Maximum Stable Set Problem in Weighted Bipartite Graphs. In DIMAP Workshop 2011, Warwick, United Kingdom, 2011. www
Non publié
- On the NP-Completeness of the Perfect Perfect Matching Free Subgraph Problem. , working paper or preprint. www
2010
Articles de revue
- A note on a conjecture on maximum matching in almost regular graphs. In Annals of Discrete Mathematics, 310: 3646-3647, 2010. www
- Blockers and Transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid. In Discrete Mathematics, 310: 132-146, 2010. doi www
- On the use of graphs in discrete tomography. In Annals of Operations Research, 175: 287-307, 2010. doi www
Livres
Articles de conférence
- Minimum d-blockers and d-transversals for the maximum stable set problem. In European conference on operational research EURO 2010, July 11-14 Lisbonne, Portugal (and ROADEF 2010 24-26 f?vrier Toulouse), pages 70-70, Libonne, Portugal, 2010. www
- On matchings and stable sets in bipartite graphs. In Graphs and Optimization VII, Ovronnaz, Suisse, pages 8-10, X, France, 2010. www
- Tomographie discrète : aspects géométriques et aspects graphiques. In Groupe de travail en G?om?trie Discr?te - GDR IM Strasbourg D?cembre 2010, pages 1, X, France, 2010. www
Rapports
- On hypochordal graphs. Technical Report CEDRIC-10-1886, CEDRIC Lab/CNAM, 2010.
2009
Articles de revue
- Graph coloring with cardinality constraints on the neighborhoods. In Discrete Optimization, 6 (4): 362-369, 2009. doi www
- The four-in-a-tree problem for triangle-free graphs. In Graphs and Combinatorics, 25: 489-502, 2009. www
- Locally bounded k -colorings of trees. In RAIRO - Operations Research, 43 (1): 27-33, 2009. doi www
- Finding Induced Trees. In Discrete Applied Mathematics, 157: 3552-3557, 2009. www
- Blockers and Transversals. In Discrete Mathematics, 13: 4306-4314, 2009. doi www
- Degree-constrained edge partitioning in graphs arising from discrete tomography. In Journal of Graph Algorithms and Applications, 13 (2): 99-118, 2009. doi www
Livres
- Précis de Recherche Opérationnelle. , 2009. www
Articles de conférence
- d-bloqueurs et d-transversaux. In Recherche op?rationnelle et aide ? la d?cision. ROADEF'09 Nancy, pages 316-317, X, France, 2009. www
- Une nouvelle classe de graphes : les hypotriangulés. In Conf?rence ROADEF 2009, Nancy, pages 2, X, France, 2009. www
2008
Articles de revue
- On a graph coloring problem arising from discrete tomography. In Networks, 51 (4): 256-267, 2008. doi www
- Addendum to ``Bicolored Matchings in Some Classes of Graphs''. In Graphs and Combinatorics, 24 (2): 127-128, 2008. doi www
- Reconstruction of binary matrices under fixed size neighborhood constraints. In Theoretical Computer Science, 406: 43-54, 2008. www
- Complexity results for the horizontal bar packing problem. In Information Processing Letters, 108 (6): 356-359, 2008. doi www
Chapitres d'ouvrage
- Small perturbations on the data of NP-complete scheduling problems. In Flexibility and Robustness in Scheduling, pages 327-340, 2008. www
Articles de conférence
- A la recherche d'un arbre induit : complexité et algorithmes. In ROADEF'08, Clermont-Ferrand, février, pages 157-158, X, France, 2008. www
- Reconstructing binary matrices with neighborhood constraints: an NP-hard problem. In IAPR'08 14th Int. Conf. on Discrete Geometry for Computer Imagery, pages 392-400, X, France, LNCS 4992 , 2008. www
- Approximating hv-convex binary matrices and images from discrete projections. In IAPR'08 14th Int. Conf. on Discrete Geometry for Computer Imagery, pages 413-422, X, France, LNCS 4992 , 2008. www
- Reconstructions tomographiques avec un nombre fixé de lignes. In ROADEF'08 - Clermont-Ferrand février, pages 365-366, X, France, 2008. www
Divers
- The four-in-a-tree problem in triangle-free graphs. , Documents de travail du Centre d'Economie de la Sorbonne 2008.23 - ISSN : 1955-611X. www
2007
Articles de revue
- Bicolored matchings in some classes of graphs. In AKCE International Journal of Graphs and Combinatorics, 23: 47-60, 2007. www
- The shortest multipaths problem in a capacitated dense channel. In European Journal of Operational Research, 178: 926-931, 2007. www
Livres
- Exercices et problèmes d'algorithmique. Dunod, 2007. www
Chapitres d'ouvrage
- Reconstruction of binary matrices under adjacency constraints. In Advances in Discrete Tomography and Its Applications, pages 125-150, 2007. www
Articles de conférence
- Reconstruction de la coloration d'un graphe `a partir des projections des voisinages. In FRANCORO/ROADEF'07, pages 87-88, Grenoble, France, 2007. www
- The Induced Steiner Tree Problem. In Graphs and Optimization VI, Cademario, Switzerland, pages 30, X, France, 2007. www
- Packing de barres horizontales. In FRANCORO/ROADEF'07, Grenoble, février, pages 153-154, X, France, 2007. www
2006
Articles de revue
- An acyclic days-off scheduling problem. In 4OR: A Quarterly Journal of Operations Research, 4: 73-85, 2006. www
- La tomographie discrète : quid ?. In Bulletin de la ROADEF: 7-10, 2006. www
- Using graphs for some discrete tomography problems. In Discrete Applied Mathematics, 154: 35-46, 2006. www
Chapitres d'ouvrage
- Ordonnancement. In Optimisation combinatoire 4 : problèmes paradigmatiques, Hermès, 2006. www
Articles de conférence
- Graph colouring with vertex neighbourhoods constraints. In Sixth Czech-Slovak Int. Symposium on Combinatorics, Graph Theory, Algorithms and Application, X, France, 2006. www
- Reconstruction de la coloration dun graphe `a partir de projections de cha^ines. In ROADEF'06 7ème congrès ROADEF - Février, pages 51, Lille, France, 2006. www
- Discrete tomography and graph coloring. In EURO XXI, Reykjavik, Iceland, X, France, 2006. www
Rapports
- Feasible node colorings of trees with cardinality constraints. Technical Report CEDRIC-06-987, CEDRIC Lab/CNAM, 2006.
2005
Articles de revue
- A solvable case of image reconstruction in discrete tomography. In Discrete Applied Mathematics, 148: 240-245, 2005. www
- Reconstruction of Convex Polyominoes from Orthogonal Projections of their Contours. In Theoretical Computer Science, 346: 439-454, 2005. www
Chapitres d'ouvrage
- Petites perturbations sur les données de problèmes d'ordonnancement NP-complets. In Flexibilité et Robustesse en Ordonnancem, pages 309-323, 2005. www
Articles de conférence
- The shortest multipaths problem in a capacitated dense channel. In ALIO/EURO'05 5th Conf. on Combinatorial Optimization, ENST, Paris, France, pages 31, X, France, 2005. www
- Reconstruction of binary matrices under adjacency constraints. In ENDM pp 281-297 Workshop on Discrete Tomography and Its Applications - New-York, USA, X, France, 2005. www
- Reconstructing an alternate periodical binary matrix from its orthogonal projections. In ICTCS 2005, Sienne, LNCS, pages 173-181, X, France, LNCS 3701 , 2005. www
- Reconstructing a binary matrix under timetabling constraints. In Workshop on Discrete Tomography and Its Applications New-York, ENDM, pages 99-112, X, France, 2005. www
- Bicolored matchings in some classes of graphs. In Int. Conf. in Graph Theory, Hyères, France, X, France, 2005. www
2004
Livres
Chapitres d'ouvrage
- Modèles et Algorithmes en Ordonnancement. In Modèles et Algorithmes en Ordonnancement, pages 228, 2004. www
Articles de conférence
- On a problem of coloured matching in regular bipartite graphs. In Contributed talk, Proceedings of Graph Theory Paris, pages 63, X, France, 2004. www
2003
Livres
- Exercices et Problèmes d'Algorithmique. Dunod, 2003. www
Chapitres d'ouvrage
- UET-UCT sur deux processeurs avec contraintes de capacité. In Ordonnancement pour l'informatique paral, pages 41-50, 2003. www
Articles de conférence
- Quelques problèmes de tomographie discrète. In Ecole d'automne de recherche opérationnelle Tours, X, France, 2003. www
2002
Articles de revue
- Flexibilité et Robustesse en Ordonnancement. In Bulletin de la ROADEF (8): 3 p, 2002. www
Articles de conférence
- On some special cases of an image reconstruction problem. In ECCO, Lugano, X, France, 2002. www
- Solving the shortest multipaths problem on grids. In CIRO Marrakech, Maroc, X, France, 2002. www
- Stabilite des problemes NP-complets. In roadef 2002, X, France, 2002. www
2001
Articles de revue
- Reconstruction of domino tiling from its two orthogonal projections. In Theoretical Computer Science, 255 (1-2): 437-447, 2001. doi www
2000
Livres
- Précis de Recherche Opérationnelle. , 2000. www
Rapports
- Reconstruction of a coloured domino tiling from its projections. Technical Report CEDRIC-00-166, CEDRIC Lab/CNAM, 2000.
- Small perturbations on some NP-complete scheduling problems. Technical Report CEDRIC-00-167, CEDRIC Lab/CNAM, 2000.
1996
Articles de revue
- Worst-case analysis of fast heuristics for packing squares into a square. In Theoretical Computer Science, 164 (1-2): 59-72, 1996. doi www
1995
Articles de revue
- New complexity results on scheduling with small communication delays. In Discrete Applied Mathematics, 60 (1-3): 331-342, 1995. doi www
1994
Articles de revue
- Complexity of the hamiltonian cycle in regular graph problem. In Theoretical Computer Science, 131 (2): 463-473, 1994. doi www