Research



I am interested in the algorithmic side of some hard problems (some slides in french here).

During my thesis, I was particularly interested in the Graph Motif problem, for which a (tentative) resume of definitions and result can be found here.

I try to maintain a list of acceptance ratio of some conferences, here.

Publications :

JabRef references
Matching entries: 0
settings...
Article
Blin, Guillaume and Bonizzoni, Paola and Dondi, Riccardo and Rizzi, Romeo and Sikora, Florian:
Complexity Insights of the Minimum Duplication Problem.
Theoretical Computer Science 2014.
BibTeX:
@article{Blin2014,
  author = {Blin, Guillaume and Bonizzoni, Paola and Dondi, Riccardo and Rizzi, Romeo and Sikora, Florian},
  title = {Complexity Insights of the Minimum Duplication Problem},
  journal = {Theoretical Computer Science},
  year = {2014},
  url = {http://hal-upec-upem.archives-ouvertes.fr/hal-00948488},
  doi = {10.1016/j.tcs.2014.02.025}
}
Blin, Guillaume and Rizzi, Romeo and Sikora, Florian and Vialette, Stéphane:
Minimum Mosaic Inference of a Set of Recombinants.
International Journal of Foundations of Computer Science (IJFCS) Vol. 24 (1) , pp. 51-66. 2013.
BibTeX:
@article{Blin2013,
  author = {Blin, Guillaume and Rizzi, Romeo and Sikora, Florian and Vialette, Stéphane},
  title = {Minimum Mosaic Inference of a Set of Recombinants},
  journal = {International Journal of Foundations of Computer Science (IJFCS)},
  year = {2013},
  volume = {24},
  number = {1},
  pages = {51-66},
  url = {http://hal-upec-upem.archives-ouvertes.fr/hal-00679269},
  doi = {10.1142/S0129054113400042}
}
Guillemot, Sylvain and Sikora, Florian:
Finding and counting vertex-colored subtrees.
Algorithmica Vol. 65 (4) , pp. 828-844. 2013.
BibTeX:
@article{guillemotfinding,
  author = {Guillemot, Sylvain and Sikora, Florian},
  title = {Finding and counting vertex-colored subtrees},
  journal = {Algorithmica},
  year = {2013},
  volume = {65},
  number = {4},
  pages = {828-844},
  url = {http://arxiv.org/abs/1002.1880},
  doi = {10.1007/s00453-011-9600-8}
}
Blin, Guillaume and Bonizzoni, Paola and Dondi, Riccardo and Sikora, Florian:
On the Parameterized Complexity of the Repetition Free Longest Common Subsequence Problem.
Information Processing Letters Vol. 112 (7) , pp. 272 - 276. 2012.
BibTeX:
@article{blin12parameterized,
  author = {Blin, Guillaume and Bonizzoni, Paola and Dondi, Riccardo and Sikora, Florian},
  title = {On the Parameterized Complexity of the Repetition Free Longest Common Subsequence Problem},
  journal = {Information Processing Letters},
  year = {2012},
  volume = {112},
  number = {7},
  pages = {272 - 276},
  url = {http://hal-upec-upem.archives-ouvertes.fr/hal-00637255},
  doi = {10.1016/j.ipl.2011.12.009}
}
Blin, Guillaume and Sikora, Florian and Vialette, Stéphane:
Querying Graphs in Protein-Protein Interactions Networks using Feedback Vertex Set.
IEEE/ACM Transactions on Computational Biology and Bioinformatics Vol. 7 (4) , pp. 628-635. IEEE Computer Society, 2010. Special Issue-ISBRA 2009-Bioinformatics Research and Applications.
BibTeX:
@article{IGMA_BliSikVia10b,
  author = {Blin, Guillaume and Sikora, Florian and Vialette, Stéphane},
  title = {Querying Graphs in Protein-Protein Interactions Networks using Feedback Vertex Set},
  journal = {IEEE/ACM Transactions on Computational Biology and Bioinformatics},
  publisher = {IEEE Computer Society},
  year = {2010},
  volume = {7},
  number = {4},
  pages = {628--635},
  note = {Special Issue-ISBRA 2009-Bioinformatics Research and Applications},
  url = {http://igm.univ-mlv.fr/~fsikora/pub/2010-TCBB.pdf},
  doi = {10.1109/TCBB.2010.53}
}
Inproceedings
Bazgan, Cristina and Chopin, Morgan and Nichterlein, André and Sikora, Florian:
Parameterized Inapproximability of Target Set Selection and Generalizations.
In Proceedings of the 10th Computability in Europe 2014. of LNCS Springer, 2014. To appear..
BibTeX:
@inproceedings{Bazgan2014,
  author = {Bazgan, Cristina and Chopin, Morgan and Nichterlein, André and Sikora, Florian},
  editor = {Arnold Beckmann, Erzsébet Csuhaj-Varjú, and Klaus Meer},
  title = {Parameterized Inapproximability of Target Set Selection and Generalizations},
  booktitle = {Proceedings of the 10th Computability in Europe 2014},
  publisher = {Springer},
  year = {2014},
  note = {To appear.},
  url = {http://arxiv.org/abs/1403.3565}
}
Bazgan, Cristina and Chopin, Morgan and Nichterlein, André and Sikora, Florian:
Parameterized Approximability of Maximizing the Spread of Influence in Networks.
In Proc. of the 19th Annual International Computing and Combinatorics Conference (COCOON'13). (7936) , pp. 543-554. Springer-Verlag, 2013.
BibTeX:
@inproceedings{Bazgan2013,
  author = {Bazgan, Cristina and Chopin, Morgan and Nichterlein, André and Sikora, Florian},
  editor = {Du, Dingzhu and Zhang, Guochuan},
  title = { Parameterized Approximability of Maximizing the Spread of Influence in Networks},
  booktitle = {Proc. of the 19th Annual International Computing and Combinatorics Conference (COCOON'13)},
  publisher = {Springer-Verlag},
  year = {2013},
  number = {7936},
  pages = {543-554},
  url = {http://arxiv.org/abs/1303.6907},
  doi = {10.1007/978-3-642-38768-5_48}
}
Blin, Guillaume and Bonizzoni, Paola and Dondi, Riccardo and Rizzi, Romeo and Sikora, Florian:
Complexity Insights of the Minimum Duplication Problem.
In Proc. of 38th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2012). Vol. 7147 of Lecture Notes in Computer Science , pp. 153-164. Springer, 2012.
Abstract: The Minimum Duplication problem is a well-known problem in phylogenetics and comparative genomics. Given a set of gene trees, the Minimum Duplication problem asks for a species tree that induces the minimum number of gene duplications in the input gene trees. More recently, a variant of the Minimum Duplication problem, called Minimum Duplication Bipartite, has been introduced in [14], where the goal is to find all pre-duplications, that is duplications that precede, in the evolution, the first speciation with respect to a species tree. In this paper, we investigate the complexity of both Minimum Duplication and Minimum Duplication Bipartite problems. First of all, we prove that the Minimum Duplication problem is APX-hard, even when the input consists of five uniquely leaf-labelled gene trees (progressing on the complexity of the problem). Then, we show that the Minimum Duplication Bipartite problem can be solved efficiently by a randomized algorithm when the input gene trees have bounded depth.
BibTeX:
@inproceedings{blin12complexity,
  author = {Blin, Guillaume and Bonizzoni, Paola and Dondi, Riccardo and Rizzi, Romeo and Sikora, Florian},
  editor = {Mária Bieliková and Gerhard Friedrich and Georg Gottlob and Stefan Katzenbeisser and György Turán and Mária Bieliková and Gerhard Friedrich and Georg Gottlob and Stefan Katzenbeisser and György Turán},
  title = {Complexity Insights of the Minimum Duplication Problem},
  booktitle = {Proc. of 38th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2012)},
  publisher = {Springer},
  year = {2012},
  volume = {7147},
  pages = {153-164},
  url = {http://hal-upec-upem.archives-ouvertes.fr/hal-00629047},
  doi = {10.1007/978-3-642-27660-6_13}
}
Rizzi, Romeo and Sikora, Florian:
Some results on more flexible versions of Graph Motif.
In Proc. of the 7th International Computer Science Symposium in Russia (CSR 2012). Vol. 7353 of Lecture Notes in Computer Science , pp. 278-289. Springer, 2012.
BibTeX:
@inproceedings{rizzi12some,
  author = {Rizzi, Romeo and Sikora, Florian},
  editor = {Edward A. Hirsch and Juhani Karhumäki and Arto Lepistö and Michail Prilutskii},
  title = {Some results on more flexible versions of Graph Motif},
  booktitle = {Proc. of the 7th International Computer Science Symposium in Russia (CSR 2012)},
  publisher = {Springer},
  year = {2012},
  volume = {7353},
  pages = {278-289},
  url = {http://arxiv.org/abs/1202.5184},
  doi = {10.1007/978-3-642-30642-6_26}
}
Yang, Xiao and Sikora, Florian and Blin, Guillaume and Hamel, Sylvie and Rizzi, Romeo and Aluru, Srinivas:
An Algorithmic View on Multi-related-segments: a unifying model for approximate common interval.
In Proc. of the 9th annual conference on Theory and Applications of Models of Computation (TAMC 2012). Vol. 7287 of Lecture Notes in Computer Science , pp. 319-329. Springer, 2012.
BibTeX:
@inproceedings{yang12algorithmic,
  author = {Yang, Xiao and Sikora, Florian and Blin, Guillaume and Hamel, Sylvie and Rizzi, Romeo and Aluru, Srinivas},
  editor = {Manindra Agrawal and S. Barry Cooper and Angsheng Li and Manindra Agrawal and S. Barry Cooper and Angsheng Li},
  title = {An Algorithmic View on Multi-related-segments: a unifying model for approximate common interval},
  booktitle = {Proc. of the 9th annual conference on Theory and Applications of Models of Computation (TAMC 2012)},
  publisher = {Springer},
  year = {2012},
  volume = {7287},
  pages = {319-329},
  url = {http://hal-upec-upem.archives-ouvertes.fr/hal-00630150},
  doi = {10.1007/978-3-642-29952-0_33}
}
Blin, Guillaume and Fertin, Guillaume and Mohamed-Babou, Hafedh and Rusu, Irena and Sikora, Florian and Vialette, Stéphane:
Algorithmic Aspects of Heterogeneous Biological Networks Comparison.
In 5th Annual International Conference on Combinatorial Optimization and Applications (COCOA'11). Vol. 6831 of Lecture Notes in Computer Science , pp. 272-286. Springer-Verlag, 2011.
BibTeX:
@inproceedings{IGMA_BliFerMoh11,
  author = {Blin, Guillaume and Fertin, Guillaume and Mohamed-Babou, Hafedh and Rusu, Irena and Sikora, Florian and Vialette, Stéphane},
  editor = {Wang, W and Zhu, X and Du, D.-Z.},
  title = {Algorithmic Aspects of Heterogeneous Biological Networks Comparison},
  booktitle = {5th Annual International Conference on Combinatorial Optimization and Applications (COCOA'11)},
  publisher = {Springer-Verlag},
  year = {2011},
  volume = {6831},
  pages = {272--286},
  url = {http://hal.archives-ouvertes.fr/hal-00606375/en},
  doi = {10.1007/978-3-642-22616-8_22}
}
Blin, Guillaume and Rizzi, Romeo and Sikora, Florian and Vialette, Stéphane:
Minimum Mosaic Inference of a Set of Recombinants.
In 17th Computing: the Australasian Theory Symposium (CATS'11). Perth Vol. 119 of CRPIT , pp. 23-30. ACS, 2011.
BibTeX:
@inproceedings{IGMA_BliRizSik10,
  author = {Blin, Guillaume and Rizzi, Romeo and Sikora, Florian and Vialette, Stéphane},
  editor = {Potanin, Alex and Viglas, Taso},
  title = {Minimum Mosaic Inference of a Set of Recombinants},
  booktitle = {17th Computing: the Australasian Theory Symposium (CATS'11)},
  publisher = {ACS},
  year = {2011},
  volume = {119},
  pages = {23--30},
  url = {http://hal.archives-ouvertes.fr/hal-00512458/fr/}
}
Blin, Guillaume and Sikora, Florian and Vialette, Stéphane:
GraMoFoNe: a Cytoscape plugin for querying motifs without topology in Protein-Protein Interactions networks.
In 2nd International Conference on Bioinformatics and Computational Biology (BICoB'10). Honolulu, USA , pp. 38-43. International Society for Computers and their Applications (ISCA), 2010.
BibTeX:
@inproceedings{IGMA_BliSikVia10,
  author = {Blin, Guillaume and Sikora, Florian and Vialette, Stéphane},
  editor = {Al-Mubaid, Hisham},
  title = {GraMoFoNe: a Cytoscape plugin for querying motifs without topology in Protein-Protein Interactions networks},
  booktitle = {2nd International Conference on Bioinformatics and Computational Biology (BICoB'10)},
  publisher = {International Society for Computers and their Applications (ISCA)},
  year = {2010},
  pages = {38--43},
  url = {http://hal.archives-ouvertes.fr/hal-00425661/fr/}
}
Guillemot, Sylvain and Sikora, Florian:
Finding and counting vertex-colored subtrees.
In 35th International Symposium on Mathematical Foundations of Computer Science (MFCS'10). Brno, Czech Republic Vol. 6281 of LNCS , pp. 405-416. Springer, 2010.
BibTeX:
@inproceedings{IGMA_GuiSik10,
  author = {Guillemot, Sylvain and Sikora, Florian},
  editor = {Hlinený, Petr and Kucera, Antonín},
  title = {Finding and counting vertex-colored subtrees},
  booktitle = {35th International Symposium on Mathematical Foundations of Computer Science (MFCS'10)},
  publisher = {Springer},
  year = {2010},
  volume = {6281},
  pages = {405--416},
  url = {http://fr.arxiv.org/abs/1002.1880},
  doi = {10.1007/978-3-642-15155-2_36}
}
Blin, Guillaume and Fertin, Guillaume and Sikora, Florian and Vialette, Stéphane:
The Exemplar Breakpoint Distance for non-trivial genomes cannot be approximated.
In 3rd Annual Workshop on Algorithms and Computation (WALCOM'09). Kolkata, India Vol. 5431 of LNCS , pp. 357-368. Springer-Verlag, 2009.
BibTeX:
@inproceedings{IGMA_BliFerSik09,
  author = {Blin, Guillaume and Fertin, Guillaume and Sikora, Florian and Vialette, Stéphane},
  editor = {Das, S. and Uehara, R.},
  title = {The Exemplar Breakpoint Distance for non-trivial genomes cannot be approximated},
  booktitle = {3rd Annual Workshop on Algorithms and Computation (WALCOM'09)},
  publisher = {Springer-Verlag},
  year = {2009},
  volume = {5431},
  pages = {357--368},
  url = {http://igm.univ-mlv.fr/~gblin/pdf/Blin_Fertin_Sikora_Vialette_WALCOM_2009.pdf},
  doi = {10.1007/978-3-642-00202-1_31}
}
Blin, Guillaume and Sikora, Florian and Vialette, Stéphane:
Querying Protein-Protein Interaction Networks.
In 5th International Symposium on Bioinformatics Research and Applications (ISBRA'09). Fort Lauderdale, FL, USA Vol. 5542 of LNBI , pp. 52-62. Springer-Verlag, 2009.
BibTeX:
@inproceedings{IGMA_BliSikVia09,
  author = {Blin, Guillaume and Sikora, Florian and Vialette, Stéphane},
  editor = {Mandoiu, Ion and Narasimhan, Giri and Zhang, Yanqing},
  title = {Querying Protein-Protein Interaction Networks},
  booktitle = {5th International Symposium on Bioinformatics Research and Applications (ISBRA'09)},
  publisher = {Springer-Verlag},
  year = {2009},
  volume = {5542},
  pages = {52--62},
  doi = {10.1007/978-3-642-01551-9_6}
}
Phdthesis
Sikora, Florian:
Aspects algorithmiques de la comparaison d'éléments biologiques.
Université Paris-Est 2011. In French.
BibTeX:
@phdthesis{Sikora2011,
  author = {Sikora, Florian},
  title = {Aspects algorithmiques de la comparaison d'éléments biologiques},
  school = {Université Paris-Est},
  year = {2011},
  note = {In French},
  url = {http://igm.univ-mlv.fr/~fsikora/these_0911.pdf}
}

Talks:

  • 2013-07 : APEX 2013: On the Parameterized Complexity of the Repetition Free Longest Common Subsequence Problem
  • 2013-06 : COCOON 2013: Parameterized Approximability of Influence in Social Networks
  • 2013-04 : JournĂ©es du LAMSADE: Comment trouver des problèmes difficiles faciles ?
  • 2012-10 : SĂ©minaire LAMSADE
  • 2012-07 : CSR - Substitution talk for Approximating minimum-power edge-multicovers.
  • 2012-07 : CSR - Some results on more flexible versions of Graph Motif.
  • 2012-04 : SĂ©minaire MabioVis, LABRI
  • 2011-09 : PhD. Thesis.
  • 2011-01 : Workshop Algorithmique, combinatoire du texte et applications en bio-informatique and CATS 2011 - Minimum Mosaic Inference of a Set of Recombinants.
  • 2010-05 : SĂ©minaire Combi LINA - Recherche de motifs dans des graphes colorĂ©s.
  • 2010-05 : SĂ©minaire LIRMM Doctorants - Recherche de motifs dans des graphes colorĂ©s.
  • 2010-05 : MSBC - GraMoFoNe: a Cytoscape plugin for querying motifs without topology in Protein-Protein Interactions networks. (Poster session)
  • 2010-03 : BICoB 10 - GraMoFoNe.
  • 2010-02 : SĂ©minaire IRISA - Symbiose - Recherche de motifs dans des graphes colorĂ©s.
  • 2009-05 : ISBRA 09 - Querying Protein-Protein Interaction Networks.
  • 2009-02 : WALCOM 09 - The Exemplar Breakpoint Distance Problem is not approximable for genomes with duplicated genes.
  • 2008-10 : RECOMB-CG 08 - The Exemplar Breakpoint Distance is not approximable... at all. (Poster session)
  • 2008-09 : Soutenance de Stage de M2.
  • 2008-05 : PrĂ©-Soutenance de Stage de M2, Ă©tat de l'art du sujet.
  • 2008-03 : PrĂ©sentation d'un article de SĂ©mon et Wolfe.

Softs (available upon request) :

Some pointers:

I was in:

CFP :