Menu

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