Number of documents

45

Publications of Laurent Bulteau


Since 2015, I am a CNRS Researcher affiliated at

Laboratoire d'Informatique Gaspard Monge, Université de Marne-la-Vallée

I was previously in:

  • Inria/Université Lyon 1 (2014-2015) as a post-doc in the Erable Team, with Marie-France Sagot 
  • T.U. Berlin (2013-2014) as a post-doc in the AKT group, with Rolf Niedermeier
  • Université de Nantes (2010-2013) as a Ph.d. student in the ComBi group, with Guillaume Fertin and Irena Rusu

 


Journal articles21 documents

  • Laurent Bulteau, Danny Hermelin, Dušan Knop, Anthony Labarre, Stéphane Vialette. The Clever Shopper Problem. Theory of Computing Systems, Springer Verlag, In press. ⟨hal-01998054⟩
  • Laurent Bulteau, Stéphane Vialette. Recognizing binary shuffle squares is NP-hard. Theoretical Computer Science, Elsevier, In press, ⟨10.1016/j.tcs.2019.01.012⟩. ⟨hal-01986646⟩
  • Laurent Bulteau, Stefan Fafianie, Vincent Froese, Rolf Niedermeier, Nimrod Talmon. The Complexity of Finding Effectors. Theory of Computing Systems, Springer Verlag, 2017, 60 (2), pp.253-279. ⟨10.1007/s00224-016-9670-8⟩. ⟨hal-01494357⟩
  • René van Bevern, Robert Bredereck, Laurent Bulteau, Jiehua Chen, Vincent Froese, et al.. Partitioning Perfect Graphs into Stars. Journal of Graph Theory, Wiley, 2017, 85 (2), pp.297-335. ⟨10.1002/jgt.22062⟩. ⟨hal-01494420⟩
  • Alice Julien-Laferrière, Laurent Bulteau, Delphine Parrot, Alberto Marchetti-Spaccamela, Leen Stougie, et al.. A Combinatorial Algorithm for Microbial Consortia Synthetic Design. Scientific Reports, Nature Publishing Group, 2016, ⟨10.1038/srep29182⟩. ⟨hal-01344296⟩
  • Laurent Bulteau, Vincent Froese, Konstantin Kutzkov, Rasmus Pagh. Triangle Counting in Dynamic Graph Streams. Algorithmica, Springer Verlag, 2016, 76 (1), pp.259 - 278. ⟨10.1007/s00453-015-0036-4⟩. ⟨hal-01494399⟩
  • Laurent Bulteau, Vincent Froese, Sepp Hartung, Rolf Niedermeier. Co-Clustering under the Maximum Norm. Algorithms, MDPI, 2016, 9 (1), pp.15 - 17. ⟨10.3390/a9010017⟩. ⟨hal-01494976⟩
  • Laurent Bulteau, Guillaume Fertin, Eric Tannier. Genome rearrangements with indels in intergenes restrict the scenario space. BMC Bioinformatics, BioMed Central, 2016, 17 (Suppl 14), 426 (7 p.). ⟨10.1186/s12859-016-1264-6⟩. ⟨hal-01396842⟩
  • Laurent Bulteau, Vincent Froese, Nimrod Talmon. Multi-Player Diffusion Games on Graph Classes. Internet Mathematics, Taylor & Francis, 2016, 12 (6), pp.363 - 380. ⟨10.1080/15427951.2016.1197167⟩. ⟨hal-01494989⟩
  • Laurent Bulteau, Guillaume Fertin, Christian Komusiewicz. (Prefix) reversal distance for (signed) strings with few blocks or small alphabets. Journal of Discrete Algorithms, Elsevier, 2016, 37, pp.44-55. ⟨10.1016/j.jda.2016.05.002⟩. ⟨hal-01318663⟩
  • Laurent Bulteau, Guillaume Fertin, Stéphane Vialette, Roméo Rizzi. Some algorithmic results for [2]-sumset covers. Information Processing Letters, Elsevier, 2015, 115 (1), pp.1-5. ⟨hal-01044891⟩
  • Laurent Bulteau, Guillaume Fertin, Irena Rusu. Pancake Flipping Is Hard. Journal of Computer and System Sciences, Elsevier, 2015, 81 (8), pp.1556-1574. ⟨10.1016/j.jcss.2015.02.003⟩. ⟨hal-01053461⟩
  • Laurent Bulteau, Anna Paola Carrieri, Riccardo Dondi. Fixed-parameter algorithms for scaffold filling. Theoretical Computer Science, Elsevier, 2015, 568, ⟨10.1016/j.tcs.2014.12.005⟩. ⟨hal-01260577⟩
  • Laurent Bulteau, Jiehua Chen, Piotr Faliszewski, Rolf Niedermeier, Nimrod Talmon. Combinatorial voter control in elections. Theoretical Computer Science, Elsevier, 2015, 589, pp.99-120. ⟨10.1016/j.tcs.2015.04.023⟩. ⟨hal-01260623⟩
  • Laurent Bulteau, Gustavo Sacomoto, Blerina Sinaimeri. Computing an Evolutionary Ordering is Hard. Electronic Notes in Discrete Mathematics, Elsevier, 2015, ⟨10.1016/j.endm.2015.07.043⟩. ⟨hal-01249259⟩
  • Laurent Bulteau, Falk Hüffner, Christian Komusiewicz, Rolf Niedermeier. Multivariate Algorithmics for NP-Hard String Problems. Bulletin- European Association for Theoretical Computer Science, European Association for Theoretical Computer Science; 1999, 2014, 114. ⟨hal-01260610⟩
  • Laurent Bulteau, Minghui Jiang. Inapproximability of (1,2)-Exemplar Distance. IEEE/ACM Transactions on Computational Biology and Bioinformatics, Institute of Electrical and Electronics Engineers, 2013, 10 (6), pp.1384-1390. ⟨10.1109/TCBB.2012.144⟩. ⟨hal-01171580⟩
  • Laurent Bulteau, Guillaume Fertin, Irena Rusu. Revisiting the Minimum Breakpoint Linearization Problem Theoretical Computer Science. Theoretical Computer Science, Elsevier, 2013, 494, pp.122-133. ⟨hal-00826880⟩
  • Laurent Bulteau, Guillaume Fertin, Irena Rusu. Maximal Strip Recovery Problem with Gaps: Hardness and Approximation Algorithms. Journal of Discrete Algorithms, Elsevier, 2013, 19, pp.1-22. ⟨hal-00826876⟩
  • Laurent Bulteau, Guillaume Fertin, Minghui Jiang, Irena Rusu. Tractability and approximability of maximal strip recovery. Theoretical Computer Science, Elsevier, 2012, 440-441, pp.14-28. ⟨10.1016/j.tcs.2012.04.034⟩. ⟨hal-00700598⟩
  • Laurent Bulteau, Guillaume Fertin, Irena Rusu. Sorting by Transpositions is Difficult. Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2012, 26 (3), pp.1148-1180. ⟨10.1137/110851390⟩. ⟨hal-00826867⟩

Conference papers20 documents

  • Laurent Bulteau, Danny Hermelin, Anthony Labarre, Stéphane Vialette. The Clever Shopper Problem. The 13th International Computer Science Symposium in Russia (CSR), Jun 2018, Moscow, Russia. ⟨hal-01715824⟩
  • Laurent Bulteau, Markus Schmid. Consensus Strings with Small Maximum Distance and Small Distance Sum. 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)., Aug 2018, Liverpool, United Kingdom. ⟨10.4230/LIPIcs.MFCS.2018.1⟩. ⟨hal-01930623⟩
  • Laurent Bulteau, Romeo Rizzi, Stéphane Vialette. Pattern Matching for k-Track Permutations. International Workshop on Combinatorial Algorithms (IWOCA), Jul 2018, Singapore, Singapore. ⟨hal-01935941⟩
  • Laurent Bulteau, Guillaume Fertin, Christian Komusiewicz. Beyond Adjacency Maximization: Scaffold Filling for New String Distances . 28th Annual Symposium on Combinatorial Pattern Matching, 2017, Warsaw, Poland. ⟨10.4230/LIPIcs.CPM.2017.27⟩. ⟨hal-01615671⟩
  • Laurent Bulteau, Guillaume Fertin, Anthony Labarre, Romeo Rizzi, Irena Rusu. Decomposing Cubic Graphs into Connected Subgraphs of Size Three. The 22nd International Computing and Combinatorics Conference (COCOON), Aug 2016, Ho Chi Minh City, Vietnam. ⟨hal-01309152⟩
  • Laurent Bulteau, Stefan Fafianie, Vincent Froese, Rolf Niedermeier, Nimrod Talmon. The Complexity of Finding Effectors. TAMC, 2015, Singapore, China. ⟨10.1007/978-3-319-17142-5_20⟩. ⟨hal-01260613⟩
  • Laurent Bulteau, Vincent Froese, Nimrod Talmon. Multi-player Diffusion Games on Graph Classes. TAMC, May 2015, Singapore, Singapore. ⟨10.1007/978-3-319-17142-5_18⟩. ⟨hal-01260620⟩
  • Laurent Bulteau, Christian Komusiewicz. Minimum Common String Partition Parameterized by Partition Size is Fixed-Parameter Tractable. SODA, 2014, University of Illinois, Urbana-Champaign, Illinois, United States. pp.102-121, ⟨10.1137/1.9781611973402.8⟩. ⟨hal-01176597⟩
  • Laurent Bulteau, Anna Paola Carrieri, Riccardo Dondi. Fixed-Parameter Algorithms for Scaffold Filling. ISCO, 2014, Lisbon, Portugal. ⟨10.1007/978-3-319-09174-7_12⟩. ⟨hal-01260583⟩
  • Laurent Bulteau, Vincent Froese, Sepp Hartung, Rolf Niedermeier. Co-Clustering Under the Maximum Norm. ISAAC, 2014, Jeonju, South Korea. ⟨10.1007/978-3-319-13075-0_24⟩. ⟨hal-01260592⟩
  • René Van Bevern, Robert Bredereck, Laurent Bulteau, Jiehua Chen, Vincent Froese, et al.. Star Partitions of Perfect Graphs. ICALP, 2014, Copenhague, Denmark. ⟨10.1007/978-3-662-43948-7_15⟩. ⟨hal-01260593⟩
  • Laurent Bulteau, Guillaume Fertin, Christian Komusiewicz. Reversal Distances for Strings with Few Blocks or Small Alphabets. 25th Annual Symposium on Combinatorial Pattern Matching (CPM 2014), Jun 2014, Moscou, Russia. pp.50-59, ⟨10.1007/978-3-319-07566-2_6⟩. ⟨hal-01044938⟩
  • Laurent Bulteau, Guillaume Fertin, Christian Komusiewicz, Irena Rusu. A Fixed-Parameter Algorithm for Minimum Common String Partition with Few Duplications. 13th Workshop on Algorithms in Bioinformatics (WABI2013), Sep 2013, Nice, France. pp.244-258, ⟨10.1007/978-3-642-40453-5_19⟩. ⟨hal-00906903⟩
  • Guillaume Blin, Laurent Bulteau, Minghui Jiang, Pedro J. Tejada, Stéphane Vialette. Hardness of longest common subsequence for sequences with bounded run-lengths. Juha Kärkkäinen and Jens Stoye. 23rd Annual Symposium on Combinatorial Pattern Matching (CPM'12), Jul 2012, Helsinki, Finland. Springer-Verlag, 7354, pp.138-148, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-31265-6_11〉. 〈hal-00683311〉
  • Laurent Bulteau, Guillaume Fertin, Irena Rusu. Pancake Flipping is Hard. 37th International Symposium on Mathematical Foundations of Computer Science (MFCS 2012), Aug 2012, Bratislava, Slovakia. pp.247-258. ⟨hal-00717712⟩
  • Laurent Bulteau, Minghui Jiang. Inapproximability of (1,2)-Exemplar Distance. Bioinformatics Research and Applications, 2012, Dallas, United States. pp.13-23, ⟨10.1007/978-3-642-30191-9_2⟩. ⟨hal-01171579⟩
  • Laurent Bulteau, Guillaume Fertin, Irena Rusu. Sorting by Transpositions is Difficult. 38th International Colloquium on Automata, Languages and Programming (ICALP 2011), 2011, Zürich, Switzerland. pp.654-665. ⟨hal-00606223⟩
  • Laurent Bulteau, Guillaume Fertin, Minghui Jiang, Irena Rusu. Tractability and Approximability of Maximal Strip Recovery. 22nd Annual Symposium on Combinatorial Pattern Matching (CPM 2011), 2011, Palermo, Italy. pp.336-349. ⟨hal-00606167⟩
  • Laurent Bulteau, Guillaume Fertin, Irena Rusu. Revisiting the Minimum Breakpoint Linearization Problem. 7th Annual Conference on Theory and Applications of Models of Computation (TAMC 2010), Jun 2010, Prague, France. pp.163-174. ⟨hal-00482856⟩
  • Laurent Bulteau, Guillaume Fertin, Irena Rusu. Maximal Strip Recovery Problem with Gaps: Hardness and Approximation Algorithms. ISAAC 2009 (20th International Symposium on Algorithms and Computation), 2009, Hawaii, United States. pp.710-719. ⟨hal-00425145⟩

Poster communications1 document

  • A Julien-Laferrière, Laurent Bulteau, D Parrot, A Marchetti-Spaccamela, L Stougie, et al.. MultiPus: Conception de communautés microbiennes pour la production de composés d'intérêt. Jobim, Jun 2016, Lyon, France. ⟨hal-01394119⟩

Book sections1 document

  • Laurent Bulteau, Konrad Dabrowski, Guillaume Fertin, Matthew Johnson, Daniël Paulusma, et al.. Finding a Small Number of Colourful Components. 30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019, 2019, ⟨10.4230/LIPIcs.CPM.2019.20⟩. ⟨hal-02304030⟩

Preprints, Working Papers, ...1 document

  • Laurent Bulteau, Konrad K. Dabrowski, Guillaume Fertin, Matthew Johnson, Daniel Paulusma, et al.. Finding a Small Number of Colourful Components. 2019. ⟨hal-01986725⟩

Theses1 document

  • Laurent Bulteau. Algorithmic Aspects of Genome Rearrangements. Data Structures and Algorithms [cs.DS]. Université de Nantes, 2013. English. ⟨tel-00906929⟩