## Publications

@misc{richoux2020automatic, primaryClass = {cs.AI}, author = {Richoux, Florian and Baffier, Jean-François}, eprint = {2002.09811}, year = {2020}, url = {https://arxiv.org/abs/2002.09811}, archivePrefix = {arXiv}, title = {Automatic Cost Function Learning with Interpretable Compositional Networks} }

#### Automatic Cost Function Learning with Interpretable Compositional Networks

Preprint Explainable AI Optimization C++
Florian Richoux, Jean-François Baffier
arXiv:2002.09811 [cs.AI].
Publication year: 2020
@inproceedings{parmentier2019introducing, organization = {Springer}, pages = {684--696}, doi = {10.1007/978-3-030-36683-4_55}, booktitle = {International Conference on Complex Networks and Their Applications}, author = {Parmentier, Pimprenelle and Viard, Tiphaine and Renoust, Benjamin and Baffier, Jean-François}, year = {2019}, title = {Introducing multilayer stream graphs and layer centralities} }

#### Introducing multilayer stream graphs and layer centralities

Conference Preprint Python Modern academics Graph theory
Pimprenelle Parmentier, Tiphaine Viard, Benjamin Renoust, Jean-François Baffier
In International Conference on Complex Networks and Their Applications, 684--696, 2019.
Publication year: 2019
@article{bae2018gapplanar, pages = {36 - 52}, author = {Bae, Sang Won and Baffier, Jean-François and Chun, Jinhee and Eades, Peter and Eickmeyer, Kord and Grilli, Luca and Hong, Seok-Hee and Korman, Matias and Montecchiani, Fabrizio and Rutter, Ignaz and Tóth, Csaba D.}, journal = {Theoretical Computer Science}, title = {Gap-planar graphs}, doi = {10.1016/j.tcs.2018.05.029}, keywords = {Beyond planarity -gap-planar graphs, Density results, Complete graphs, Recognition problem, -planar graphs, -quasiplanar graphs}, issn = {0304-3975}, year = {2018}, url = {http://www.sciencedirect.com/science/article/pii/S0304397518303670}, volume = {745}, abstract = {We introduce the family of $$k$$-gap-planar graphs for $$k\ge 0$$, i.e., graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge is assigned at most $$k$$ of its crossings. This definition is motivated by applications in edge casing, as a $$k$$-gap-planar graph can be drawn crossing-free after introducing at most $$k$$ local gaps per edge. We present results on the maximum density of $$k$$-gap-planar graphs, their relationship to other classes of beyond-planar graphs, characterization of $$k$$-gap-planar complete graphs, and the computational complexity of recognizing $$k$$-gap-planar graphs.} }
##### Gap-planar graphs

We introduce the family of $$k$$-gap-planar graphs for $$k\ge 0$$, i.e., graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge is assigned at most $$k$$ of its crossings. This definition is motivated by applications in edge casing, as a $$k$$-gap-planar graph can be drawn crossing-free after introducing at most $$k$$ local gaps per edge. We present results on the maximum density of $$k$$-gap-planar graphs, their relationship to other classes of beyond-planar graphs, characterization of $$k$$-gap-planar complete graphs, and the computational complexity of recognizing $$k$$-gap-planar graphs.

#### Gap-planar graphs

Journal Preprint Graph theory
Sang Won Bae, Jean-François Baffier, Jinhee Chun, Peter Eades, Kord Eickmeyer, Luca Grilli, Seok-Hee Hong, Matias Korman, Fabrizio Montecchiani, Ignaz Rutter, Csaba D. Tóth
Theoretical Computer Science, 745, 36 - 52, 2018.
Publication year: 2018
@inproceedings{baffier2018experimental, pages = {19:1--19:13}, booktitle = {17th International Symposium on Experimental Algorithms (SEA 2018)}, author = {Baffier, Jean-François and Diez, Yago and Korman, Matias}, editor = {D'Angelo, Gianlorenzo}, title = {Experimental Study of Compressed Stack Algorithms in Limited Memory Environments}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, doi = {10.4230/LIPIcs.SEA.2018.19}, address = {Dagstuhl, Germany}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, year = {2018}, volume = {103} }

#### Experimental Study of Compressed Stack Algorithms in Limited Memory Environments

Conference Preprint C++ Compressed data structures
Jean-François Baffier, Yago Diez, Matias Korman
In 17th International Symposium on Experimental Algorithms (SEA 2018), Leibniz International Proceedings in Informatics (LIPIcs), 19:1--19:13, Dagstuhl, Germany, 2018. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik.
Publication year: 2018
@inproceedings{baffier2018bilevel, pages = {105 - 114}, doi = {10.1016/j.endm.2018.01.012}, booktitle = {Electronic Notes in Discrete Mathematics}, author = {Baffier, Jean-François and Poirion, Pierre-Louis and Suppakitpaisarn, Vorapong}, note = {8th International Network Optimization Conference - INOC 2017}, year = {2018}, volume = {64}, title = {Bilevel Model for Adaptive Network Flow Problem} }

#### Bilevel Model for Adaptive Network Flow Problem

Conference Julia Network interdiction Graph theory Optimization
Jean-François Baffier, Pierre-Louis Poirion, Vorapong Suppakitpaisarn
In Electronic Notes in Discrete Mathematics, 105 - 114, 2018.
Publication year: 2018
@article{renoust2017multiplex, pages = {23}, author = {Renoust, Benjamin and Claver, Vivek and Baffier, Jean-François}, day = {18}, month = {Jul}, journal = {Applied Network Science}, title = {Multiplex flows in citation networks}, number = {1}, doi = {10.1007/s41109-017-0035-2}, year = {2017}, volume = {2} }

#### Multiplex flows in citation networks

Journal Python C++ Graph theory Modern academics
Benjamin Renoust, Vivek Claver, Jean-François Baffier
Applied Network Science, 2(1), 23, 2017.
Publication year: 2017
@article{baffier2017hanabi, publisher = {Elsevier}, pages = {43--55}, author = {Baffier, Jean-François and Chiu, Man-Kwun and Diez, Yago and Korman, Matias and Mitsou, Valia and van Renssen, André and Roeloffzen, Marcel and Uno, Yushi}, year = {2017}, volume = {675}, journal = {Theoretical Computer Science}, title = {Hanabi is np-hard, even for cheaters who look at their cards} }

#### Hanabi is np-hard, even for cheaters who look at their cards

Journal Preprint Game analysis
Jean-François Baffier, Man-Kwun Chiu, Yago Diez, Matias Korman, Valia Mitsou, André van Renssen, Marcel Roeloffzen, Yushi Uno
Theoretical Computer Science, 675, 43--55, 2017.
Publication year: 2017
@inproceedings{renoust2017flows, pages = {159--170}, booktitle = {Complex Networks & Their Applications V}, author = {Renoust, Benjamin and Claver, Vivek and Baffier, Jean-François}, isbn = {978-3-319-50901-3}, title = {Flows of Knowledge in Citation Networks}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-319-50901-3_13}, address = {Cham}, year = {2017} }

#### Flows of Knowledge in Citation Networks

Conference Python C++ Graph theory Modern academics
Benjamin Renoust, Vivek Claver, Jean-François Baffier
In Complex Networks & Their Applications V, 159--170, Cham, 2017. Springer International Publishing.
Publication year: 2017
@article{baffier2016parametric, pages = {20 - 36}, author = {Baffier, Jean-François and Suppakitpaisarn, Vorapong and Hiraishi, Hidefumi and Imai, Hiroshi}, journal = {Discrete Optimization}, title = {Parametric multiroute flow and its application to multilink-attack network}, doi = {10.1016/j.disopt.2016.05.002}, keywords = {Graph and network algorithm, Approximation algorithm, Network flow, Network interdiction, Multiroute flow, Parametric optimization}, issn = {1572-5286}, note = {SI: ISCO 2014}, year = {2016}, url = {http://www.sciencedirect.com/science/article/pii/S1572528616300330}, volume = {22}, abstract = {We investigate variants of the max-flow problem in a network under $$k$$ attacks. The network interdiction problem is to find the minimum max-flow value among $$mk$$ networks that can be obtained by deleting each set of $$k$$ links. The adaptive network flow problem is to find a flow of the network such that the flow value is maximum against any set of $$k$$ links attack, when deleting the corresponding flow to those $$k$$ links in the original flow. First, we prove that max-$$(k+1)$$-route flow is a $$(k+1)$$-approximation for both problems. Also, we develop a polynomial-time heuristic algorithm for both cases, called the iterative multiroute flow. Then in a second phase, we investigate properties of the function taking the real value $$h$$ to the max $$h$$-route flow value, and apply the result to solve both of the problems. We show that the function is piecewise hyperbolic, and modify a standard parametric optimization technique to find this function. The running time of the algorithm is $$O(\lambda T)$$, when $$\lambda$$ is a source–sink edge connectivity of our network and $$T$$ the computation time of a max-flow algorithm. We show that for some instances, when $$h$$ is optimally chosen, the max-$$h$$-route flow is an exact solution for both problems.} }
##### Parametric multiroute flow and its application to multilink-attack network

We investigate variants of the max-flow problem in a network under $$k$$ attacks. The network interdiction problem is to find the minimum max-flow value among $$mk$$ networks that can be obtained by deleting each set of $$k$$ links. The adaptive network flow problem is to find a flow of the network such that the flow value is maximum against any set of $$k$$ links attack, when deleting the corresponding flow to those $$k$$ links in the original flow. First, we prove that max-$$(k+1)$$-route flow is a $$(k+1)$$-approximation for both problems. Also, we develop a polynomial-time heuristic algorithm for both cases, called the iterative multiroute flow. Then in a second phase, we investigate properties of the function taking the real value $$h$$ to the max $$h$$-route flow value, and apply the result to solve both of the problems. We show that the function is piecewise hyperbolic, and modify a standard parametric optimization technique to find this function. The running time of the algorithm is $$O(\lambda T)$$, when $$\lambda$$ is a source–sink edge connectivity of our network and $$T$$ the computation time of a max-flow algorithm. We show that for some instances, when $$h$$ is optimally chosen, the max-$$h$$-route flow is an exact solution for both problems.

#### Parametric multiroute flow and its application to multilink-attack network

Journal Julia Network interdiction Graph theory
Jean-François Baffier, Vorapong Suppakitpaisarn, Hidefumi Hiraishi, Hiroshi Imai
Discrete Optimization, 22, 20 - 36, 2016.
Publication year: 2016
@article{richoux2016ghost, pages = {1-1}, author = {Richoux, Florian and Uriarte, Alberto and Baffier, Jean-François}, journal = {IEEE Transactions on Computational Intelligence and AI in Games}, title = {GHOST: A Combinatorial Optimization Framework for RTS-related Problems}, number = {99}, doi = {10.1109/TCIAIG.2016.2573199}, year = {2016}, volume = {PP}, annote = {\small GHOST is a competitive combinatorial optimization framework that a real-time strategy (RTS) AI developer can use to model and solve any problem encoded as a constraint satisfaction/optimization problem (CSP/COP).} }

#### GHOST: A Combinatorial Optimization Framework for RTS-related Problems

Journal Preprint C++ Game Explainable AI
Florian Richoux, Alberto Uriarte, Jean-François Baffier
IEEE Transactions on Computational Intelligence and AI in Games, PP(99), 1-1, 2016.
Publication year: 2016
@inproceedings{baffier2016implementation, booktitle = {The 9th Annual Meeting of Asian Association For Algorithms and Computation, Taipei, Taiwan}, author = {Baffier, Jean-François and Diez, Yago and Korman, Matias}, year = {2016}, title = {Implementation of a Stack Structure with Limited Memory} }

#### Implementation of a Stack Structure with Limited Memory

Conference Julia Compressed data structures
Jean-François Baffier, Yago Diez, Matias Korman
In The 9th Annual Meeting of Asian Association For Algorithms and Computation, Taipei, Taiwan, 2016.
Publication year: 2016
@inproceedings{baffier2016hanabi, pages = {4:1--4:17}, doi = {10.4230/LIPIcs.FUN.2016.4}, booktitle = {8th International Conference on Fun with Algorithms, FUN 2016, June 8-10, 2016, La Maddalena, Italy}, author = {Baffier, Jean-François and Chiu, Man-Kwun and Diez, Yago and Korman, Matias and Mitsou, Valia and Renssen, André and Roeloffzen, Marcel and Uno, Yushi}, year = {2016}, title = {Hanabi is NP-complete, Even for Cheaters who Look at Their Cards} }

#### Hanabi is NP-complete, Even for Cheaters who Look at Their Cards

Conference Game analysis
Jean-François Baffier, Man-Kwun Chiu, Yago Diez, Matias Korman, Valia Mitsou, André Renssen, Marcel Roeloffzen, Yushi Uno
In 8th International Conference on Fun with Algorithms, FUN 2016, June 8-10, 2016, La Maddalena, Italy, 4:1--4:17, 2016.
Publication year: 2016
@article{suppakitpaisarn2015speeding, number = {4}, pages = {111-116}, doi = {10.1587/comex.4.111}, author = {Suppakitpaisarn, Vorapong and Baffier, Jean-François}, year = {2015}, volume = {4}, journal = {IEICE Communications Express}, title = {Speeding up algorithm for maximizing barrier coverage using parametric multiroute flow} }

#### Speeding up algorithm for maximizing barrier coverage using parametric multiroute flow

Journal Julia Network interdiction Graph theory
Vorapong Suppakitpaisarn, Jean-François Baffier
IEICE Communications Express, 4(4), 111-116, 2015.
Publication year: 2015
@inproceedings{suppakitpaisarn2015robust, pages = {40--47}, doi = {10.1109/HPSR.2015.7483079}, booktitle = {16th IEEE International Conference on High Performance Switching and Routing, {HPSR} 2015, Budapest, Hungary, July 1-4, 2015}, author = {Suppakitpaisarn, Vorapong and Dai, Wenkai and Baffier, Jean-François}, year = {2015}, title = {Robust network flow against attackers with knowledge of routing method} }

#### Robust network flow against attackers with knowledge of routing method

Conference Julia Network interdiction Graph theory
Vorapong Suppakitpaisarn, Wenkai Dai, Jean-François Baffier
In 16th IEEE International Conference on High Performance Switching and Routing, {HPSR} 2015, Budapest, Hungary, July 1-4, 2015, 40--47, 2015.
Publication year: 2015
@inproceedings{baffier2015algorithms, pages = {251--258}, doi = {10.1109/RNDM.2015.7325237}, booktitle = {7th International Workshop on Reliable Networks Design and Modeling, RNDM 2015, Munich, Germany, October 5-7, 2015}, author = {Baffier, Jean-François and Suppakitpaisarn, Vorapong}, year = {2015}, title = {Algorithms for finding robust and sustainable network flows against multilink-attack} }

#### Algorithms for finding robust and sustainable network flows against multilink-attack

Conference Julia Network interdiction Graph theory
Jean-François Baffier, Vorapong Suppakitpaisarn
In 7th International Workshop on Reliable Networks Design and Modeling, RNDM 2015, Munich, Germany, October 5-7, 2015, 251--258, 2015.
Publication year: 2015
@phdthesis{baffier2015thesis, school = {The University of Tokyo (東京大学)}, author = {Baffier, Jean-François}, year = {2015}, title = {Extended Multiroute Flow for Multilink Attack Networks} }

#### Extended Multiroute Flow for Multilink Attack Networks

Thesis Network interdiction Julia C++ Graph theory
Jean-François Baffier
PhD thesis, The University of Tokyo (東京大学), 2015.
Publication year: 2015
@inbook{gragera2015skull, pages = {1--4}, booktitle = {Encyclopedia of Computer Graphics and Games}, author = {Gragera Aguaza, Alonso and Baffier, Jean-François and Suppakitpaisarn, Vorapong}, editor = {Lee, Newton}, title = {Skull and Roses Card Game}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-319-08234-9_19-1}, address = {Cham}, year = {2015} }

#### Skull and Roses Card Game

Chapter Game analysis
Alonso Gragera Aguaza, Jean-François Baffier, Vorapong Suppakitpaisarn
Encyclopedia of Computer Graphics and Games, 1--4, Springer International Publishing, Cham.
Publication year: 2015
@inproceedings{baffier2014parametric, pages = {26--37}, doi = {10.1007/978-3-319-09174-7_3}, booktitle = {Combinatorial Optimization - Third International Symposium, ISCO 2014, Lisbon, Portugal, March 5-7, 2014, Revised Selected Papers}, author = {Baffier, Jean-François and Suppakitpaisarn, Vorapong and Hiraishi, Hidefumi and Imai, Hiroshi}, year = {2014}, title = {Parametric Multiroute Flow and Its Application to Robust Network with $$k$$ Edge Failures} }

#### Parametric Multiroute Flow and Its Application to Robust Network with $$k$$ Edge Failures

Conference Julia Network interdiction Graph theory
Jean-François Baffier, Vorapong Suppakitpaisarn, Hidefumi Hiraishi, Hiroshi Imai
In Combinatorial Optimization - Third International Symposium, ISCO 2014, Lisbon, Portugal, March 5-7, 2014, Revised Selected Papers, 26--37, 2014.
Publication year: 2014
@inproceedings{baffier2014approximation, pages = {68--79}, doi = {10.1007/978-3-319-04657-0_9}, booktitle = {Algorithms and Computation - 8th International Workshop, WALCOM 2014, Chennai, India, February 13-15, 2014, Proceedings}, author = {Baffier, Jean-François and Suppakitpaisarn, Vorapong}, year = {2014}, title = {A $$(k + 1)$$-Approximation Robust Network Flow Algorithm and a Tighter Heuristic Method Using Iterative Multiroute Flow} }

#### A $$(k + 1)$$-Approximation Robust Network Flow Algorithm and a Tighter Heuristic Method Using Iterative Multiroute Flow

Conference Julia Network interdiction Graph theory
Jean-François Baffier, Vorapong Suppakitpaisarn
In Algorithms and Computation - 8th International Workshop, WALCOM 2014, Chennai, India, February 13-15, 2014, Proceedings, 68--79, 2014.
Publication year: 2014