Publications

Ioan Todinca

Univ. Orléans, France


Cf. également les pages DBLP , Google Scholar, HAL ou MathSciNet. Les fichiers PDF ou PS correspondent aux pré-versions soumises.

Soumis

  1. Deterministic graph connectivity in the broadcast congested clique, with Pedro Montealegre. CoRR abs/1602.04095 (2016).

Revues

  1. Large Induced Subgraphs via Triangulations and CMSO, with Fedor V. Fomin and Yngve Villanger. SIAM J. Comput. 44(1): 54-87 (2015).
  2. Allowing each node to communicate only once in a distributed system: shared whiteboard models, with Florent Becker, Adrian Kosowski, Martin Matamala, Nicolas Nisse, Ivan Rapaport, Karol Suchan. Distributed Computing 28(3): 189-200 (2015).
  3. Injective coloring with arithmetic constraints, with Natacha Astromujoff, Mathieu Chapelle, Martin Matamala and Jose Zamora. Graphs and Combinatorics 31(6): 2003-2017 (2015).
  4. (Circular) backbone colouring: tree backbones in planar graphs, with Frédéric Havet, Andrew D. King and Mathieu Liedloff. Discrete Applied Mathematics 169: 119-134 (2014). pdf
  5. Solving Capacitated Dominating Set by Using Covering by Subsets and Maximum Matching, with Mathieu Liedloff and Yngve Villanger. Accepted in Discrete Applied Mathematics.
  6. An O(n^2) algorithm for the minimal interval completion problem, with C. Crespelle. Theoretical Computer Science 494: 75-85 (2013). pdf
  7. The complexity of the bootstraping percolation and other problems, with Eric Goles and Pedro Montealegre-Barba. Theoretical Computer Science 504: 73-82 (2013).
  8. A note on planar graphs with large width parameters and small grid-minors, with Alexander Grigoriev, Bert Marchal, Natalya Usotskaya. Discrete Applied Mathematics 168: 60-68 (2012).
  9. On Dissemination Thresholds in Regular and Irregular Graph Classes, vith Ivan Rapaport, Karol Suchan and Jacques Verstraëte. Algorithmica 59(1): 16-34 (2011).
  10. Exponential time algorithms for the minimum dominating set problem on some graph classes, with Serge Gaspers, Dieter Kratsch and Mathieu Liedloff. ACM Transactions on Algorithms 6(1) (2009).
  11. Computing branchwidth via efficient triangulations and blocks, with F. Fomin and F. Mazoit. Discrete Applied Mathematics 157(12): 2726-2736 (2009).
  12. Minimal interval completion through graph exploration, with K. Suchan. Theoretical Computer Science 410(1): 35-43 (2009).
  13. Feedback vertex set on AT-free graphs, with D. Kratsch and H. Müller. Discrete Applied Mathematics 156(10): 1936-1947 (2008).
  14. Minimal proper interval completions, with I. Rapaport and K. Suchan. Information Processing Letters106(5): 195-202 (2008).
  15. Exact Algorithms for Treewidth and Minimum Fill-In, with F. Fomin, D. Kratsch and Y. Villanger. SIAM Journal on Computing 38(3): 1058-1079 (2008).
  16. On powers of graphs of bounded NLC-width (clique-width), with K. Suchan. Discrete Applied Mathematics 155 (14): 1885-1893 (2007). ps
  17. On treewidth approximations, with V. Bouchitté, D. Kratsch, H. Müller. Discrete Applied Mathematics 136 (2-3): 183-196 (2004). ps
  18. Chordal embeddings of planar graphs, with V. Bouchitté, F. Mazoit. Discrete Mathematics 273 (1-3): 85-102 (2003). ps
  19. Approximating the treewidth of AT-free graphs, with V. Bouchitté. Discrete Applied Mathematics 131 (1-5): 11-37 (2003).  ps
  20. Listing all potential maximal cliques of a graph, with V. Bouchitté.  Theoretical Computer Science 276(1-2): 17-32 (2001).  ps
  21. Treewidth and minimum fill-in: grouping the minimal separators, with V. Bouchitté.  SIAM J. on Computing 31(1): 212-323 (2001).  ps

Actes de colloques

Une partie de ces articles sont des versions prémilinaires des publications journaux sus-citées.
  1. Algorithms Parameterized by Vertex Cover and Modular Width, through Potential Maximal Cliques, with Fedor V. Fomin, Mathieu Liedloff, Pedro Montealegre-Barba. SWAT 2014: 182-193
  2. Large induced subgraphs via triangulations and CMSO, with Fedor Fomin and Yngve Villanger. SODA 2014: 582-593.
  3. Treewidth and Pathwidth parameterized by the Vertex Cover Number, with Mathieu Chapelle, Mathieu Liedloff and Yngve Villanger. WADS 2013: 232-243.
  4. Exact Algorithm for the Maximum Induced Planar Subgraph Problem, with Fedor Fomin and Yngve Villanger. ESA 2011: 287-298.
  5. Adding a Referee to an Interconnection Network: What Can(not) Be Computed in One Round, with Florent Becker, Martin Matamala, Nicolas Nisse, Ivan Rapaport and Karol Suchan. IPDPS 2011: 508-514.
  6. An O(n^2)-time Algorithm for the Minimal Interval Completion Problem, with Christophe Crespelle. TAMC 2010: 175-186.
  7. Solving Capacitated Dominating Set by Using Covering by Subsets and Maximum Matching, with Mathieu Liedloff and Yngve Villanger. WG 2010: 88-99.
  8. Constructing Brambles, with M. Chapelle and F. Mazoit. Proceedings 34th International Symposium on Mathematical Foundations of Computer Science (MFCS'09), Volume 5734 of LNCS, 223-234, 2009. pdf
  9. Pathwidth is NP-Hard for Weighted Trees, with R. Mihai. Proceedings 3rd International Workshop: Frontiers in Algorithms (FAW'09), Volume 5598 of LNCS, 181-195, 2009. pdf
  10. On Dissemination Thresholds in Regular and Irregular Graph Classes, with I. Rapaport, K. Suchan, J. Verstraëte. Proceedings 8th Latin American Symposium on Theoretical Informatics (LATIN'08), Volume 4957 of LNCS, 24-35, 2008.
  11. Pathwidth of circular-arc graphs, with K. Suchan. Proceedings 33nd International Workshop on Graph-Theoretic Aspects in Computer Science (WG'07), Volume 4769 of LNCS, 258-269, 2007. pdf
  12. Characterizing minimal interval completions. Towards better understanding of profile and pathwidth, with P. Heggernes, K. Suchan and Y. Villanger. Proceedings 24th Symposium on Theoretical Aspects in Computer Science (STACS'07), Volume 4393 of LNCS, 236-247, 2007. ps
  13. Minimal initerval completions through graph exploration, with K. Suchan. Proceedings 17th International Symposium on Algorithms and Computation (ISAAC'06) , Volume 4288 of LNCS, 517-526, 2006. pdf
  14. Minimal proper interval completions, with I. Rapaport and K. Suchan. Proceedings 32nd International Workshop on Graph-Theoretic Aspects in Computer Science (WG'06) , Volume 4271 of LNCS, 217-228, 2006. pdf
  15. Minimal interval completions, with P. Heggernes, K. Suchan and Y. Villanger. Proceedings 13th European Symposium on Algorithms (ESA 2005), volume 3669 of LNCS, 403-414, 2005. ps
  16. Computing branchwidth via Efficient Triangulations and blocks, with F. Fomin and  F. Mazoit.  Proceedings 31st International Workshop on Graph-Theoretic Aspects in Computer Science (WG'05), volume 3787 of LNCS, 374-384, 2005. ps
  17. Exact (Exponential) Algorithms for Treewidth and Minimum Fill-In, with D. Kratsch and F. Fomin. Proceedings 31st International Colloquium on Automatas, Languages and Programming (ICALP 2004), volume 3142 of LNCS, 568-580, 2004. ps
  18. Feedback Vertex Set and Longest Induced Path on AT-Free Graphs, with D. Kratsch, H. Müller.  Proceedings 29th International Workshop on Graph-Theoretic Aspects in Computer Science (WG'03), volume 2880 of LNCS, 309-321, 2003. ps
  19. Coloring Powers of Graphs of Bounded Clique-WidthProceedings 29th International Workshop on Graph-Theoretic Aspects in Computer Science (WG'03), volume 2880 of LNCS, 370-382, 2003. ps
  20. Approximating the treewidth of AT-free graphs, with V. Bouchitté. Proceedings 26th International Workshop on Graph-Theoretic Aspects in Computer Science (WG'00), volume 1928 of LNCS, 59-70, 2000. ps
  21. Listing all potential maximal cliques of a graph, with V. Bouchitté. Proceedings 17th Symposium on Theoretical Aspects in Computer Science (STACS 2000), volume 1770 of LNCS, 503-515, 2000. ps
  22. Treewidth and Minimum Fill-in of Weakly Triangulated Graphs, with Vincent Bouchitté. Proceedings 16th Symposium on Theoretical Aspects in Computer Science (STACS'99), volume 1563 of LNCS, 197-206, 1999. ps
  23. Minimal Triangulations for Graphs with "Few" Minimal Separators, with V. Bouchitté. Proceedings 6th European Symposium on Algorithms (ESA'98), volume 1461 of LNCS, 344-355, 1998. ps

Articles courts

  1. Connected search in outerplanar graphs, with F. Fomin and D. Thilikos. 7th International Colloquium on Graph Theory (ICGT 2005)ps
  2. Treewidth of planar graphs: connections with duality, with V. Bouchitté, F. Mazoit. EuroConference on Combinatorics, Graph Theory and Applications (COMB'01). ps
  3. On treewidth approximations, with V.Bouchitté, D. Kratsch, H. Müller. Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW'01). ps
  4. Treewidth: using the potential maximal cliques, with V. Bouchitté. Journées de l'Informatique Messine (JIM 2000). ps

Thèses

  • Décompositions arborescentes de graphes : calculs, approximations, heuristiques, Habilitation thesis, defended on December 1st, 2006 at the University of Orléans. PostScript (in french).
  • Aspects algorithmiques des triangulations minimales des graphes, PhD thesis, defended on January 15th, 1999 at the École Normale Supérieure de Lyon. PostScript (in french).