Publications

2026

1. 

   Computational Generation of Substrate-Specific Molecular Cages

   Noé Demange, Yann Strozecki, and Sandrine Vial

   In 24th International Symposium on Experimental Algorithms (SEA 2026), 2026

   Abs DOI arXiv Bib Slides

   In this paper, we propose a method to build molecular cages designed to capture a specific substrate. We model a cage as a graph of atoms with coordinates in space, and several constraints on their edges (degree, length and angle). We use a simple method to place binding patterns which are able to interact with certain parts of the substrate. We then propose an algorithm which considers all possible ways of connecting these binding patterns and try to construct the smallest possible molecular paths realizing these connections. We investigate many variants of our method in order to obtain the most efficient algorithm, able to build cages of more than a hundred atoms.

   @inproceedings{demange_et_al:LIPIcs.SEA.2026.15,
     author = {Demange, No\'{e} and Strozecki, Yann and Vial, Sandrine},
     title = {{Computational Generation of Substrate-Specific Molecular Cages}},
     booktitle = {24th International Symposium on Experimental Algorithms (SEA 2026)},
     pages = {15:1--15:21},
     series = {Leibniz International Proceedings in Informatics (LIPIcs)},
     isbn = {978-3-95977-422-2},
     issn = {1868-8969},
     year = {2026},
     volume = {371},
     editor = {Aum\"{u}ller, Martin and Finocchi, Irene},
     publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
     address = {Dagstuhl, Germany},
     url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.15},
     urn = {urn:nbn:de:0030-drops-260191},
     doi = {10.4230/LIPIcs.SEA.2026.15},
     annote = {Keywords: Enumeration, Molecular Cage, Cheminformatics, Geometric Algorithms, Experimental Algorithms},
   }

2. Complexity of Finding and Enumerating Interconnection Trees

   Noé Demange and Yann Strozecki

   arXiv preprint arXiv:2605.18125, 2026

   Abs arXiv Bib

   We study the problem of connecting the parts of a multipartite graph using a minimum number of edges under a matching constraint. We introduce interconnection trees, defined as matchings whose projections onto the quotient graph form a spanning tree. Motivated by applications in chemoinformatics, we investigate the decision, counting, and enumeration variants of this problem. We show that the decision problem is -complete. Nevertheless, it becomes tractable in several structured settings: it is fixed-parameter tractable in the number of parts, and admits polynomial or linear-time algorithms on complete, quasi-complete, and -quasi-complete multipartite graphs. We also study enumeration, for which we design efficient flashlight-search based algorithms with optimal delay for complete multipartite graphs, and a weight-guided heuristic that prioritizes low-weight solutions and performs well in practice.

   @article{demange-2026-2,
     author = {Demange, Noé and Strozecki, Yann},
     title = {Complexity of Finding and Enumerating Interconnection Trees},
     journal = {arXiv preprint arXiv:2605.18125},
     year = {2026},
     url = {https://arxiv.org/abs/2605.18125},
   }

2024

1. Génération de guides de construction de cages moléculaires

   Noé Demange

   2024

   Bib Poster

   @misc{demange-2024,
     author = {Demange, Noé},
     title = {Génération de guides de construction de cages moléculaires},
     year = {2024},
   }