Journal Papers

  • Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs.
    Pinar Heggernes, Daniel Meister, and Charis Papadopoulos.
    Discrete Applied Mathematics, in press (pdf).
  • Graphs of linear clique-width at most 3.
    Pinar Heggernes, Daniel Meister, and Charis Papadopoulos.
    Theoretical Comuter Science 412: 5466--5486, 2011 (pdf).
  • Cutwidth of split graphs and threshold graphs.
    Pinar Heggernes, Daniel Lokshtanov, Rodica Mihai, and Charis Papadopoulos.
    SIAM Journal on Discrete Mathematics 25: 1418--1437, 2011 (pdf).
  • Strongly chordal and chordal bipartite graphs are sandwich monotone.
    Pinar Heggernes, Federico Mancini, Charis Papadopoulos, and R. Sritharan.
    Journal of Combinatorial Optimization 22: 438-456, 2011 (pdf).
  • A simple linear-time recognition algorithm for weakly quasi-threshold graphs.
    Stavros D. Nikolopoulos and Charis Papadopoulos.
    Graphs and Combinatorics 27: 557-565, 2011 (pdf).
  • Characterizing and computing minimal cograph completions.
    Daniel Lokshtanov, Federico Mancini, and Charis Papadopoulos.
    Discrete Applied Mathematics 158: 755-764, 2010 (pdf).
  • Clustering with partial information.
    Hans Bodlaender, Mike Fellows, Pinar Heggernes, Federico Mancini, Charis Papadopoulos, and Fran Rosamond.
    Theoretical Computer Science 411: 1202-1211, 2010 (pdf).
  • Maximizing the number of spanning trees in Kn-complements of asteroidal graphs.
    Stavros D. Nikolopoulos, Leonidas Palios, and Charis Papadopoulos.
    Discrete Mathematics 309: 3049-3060, 2009 (pdf).
  • Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions.
    Pinar Heggernes and Charis Papadopoulos.
    Theoretical Computer Science 410: 1-15, 2009 (pdf).
  • Counting spanning trees in cographs: An algorithmic approach.
    Stavros D. Nikolopoulos and Charis Papadopoulos.
    Ars Combinatoria 90: 257-274, 2009 (pdf).
  • Minimal comparability completions of arbitrary graphs.
    Pinar Heggernes, Federico Mancini, and Charis Papadopoulos.
    Discrete Applied Mathematics 156: 705 - 718, 2008 (pdf).
  • Drawing graphs using modular decomposition.
    Charis Papadopoulos and Constantinos Voglis.
    Journal of Graph Algorithms and Applications 11: 481 - 511, 2007 (pdf).
  • An optimal parallel solution for the path cover problem on P4-sparse graphs.
    Katerina Asdre, Stavros D. Nikolopoulos, and Charis Papadopoulos.
    Journal of Parallel and Distributed Computing 67: 63 - 76, 2007 (pdf).
  • On the number of spanning trees of K+/-G graphs.
    Stavros D. Nikolopoulos and Charis Papadopoulos.
    Discrete Mathematics & Theoretical Computer Science 8: 235 - 248, 2006 (pdf).
  • The number of spanning trees in Kn-complements of quasi-threshold graphs.
    Stavros D. Nikolopoulos and Charis Papadopoulos.
    Graphs and Combinatorics 20: 383 - 397, 2004 (pdf).
  • On the performance of the first-fit coloring algorithm on permutation graphs.
    Stavros D. Nikolopoulos and Charis Papadopoulos.
    Information Processing Letters 75: 265 - 273, 2000 (pdf).

Refereed Conference Papers

  • Enumerating minimal subset feedback vertex sets.
    Fedor Fomin, Pinar Heggernes, Dieter Kratsch, Charis Papadopoulos, and Yngve Villanger
    Algorithms and Data Structures Symposium, (WADS 2011), New York, U.S.A, 2011. Springer Verlag, LNCS 6844: 399-410 (pdf).
  • Counting spanning trees in graphs using modular decomposition.
    Stavros D. Nikolopoulos, Leonidas Palios, and Charis Papadopoulos.
    Workshop on Algorithms and Computation, (WALCOM 2011), New Delhi, India, 2011. Springer Verlag, LNCS 6552: 202-213 (pdf).
  • A simple linear-time recognition algorithm for weakly quasi-threshold graphs.
    Stavros D. Nikolopoulos and Charis Papadopoulos.
    8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, (CTW 2009), Ecole Polytechnique and CNAM, Paris, France, pp. 23-27, 2009 (pdf).
  • Strongly chordal and chordal bipartite graphs are sandwich monotone.
    Pinar Heggernes, Federico Mancini, Charis Papadopoulos, and R. Sritharan.
    15th International Computing and Combinatorics Conference, (COCOON 2009), Niagara Falls, New York, U.S.A., 2009. Springer Verlag, LNCS 5609: 398-407 (pdf).
  • A complete characterisation of the linear clique-width of path powers.
    Pinar Heggernes, Daniel Meister, and Charis Papadopoulos.
    6th Annual Conf. on Theory and Applications of Models of Computation, (TAMC 2009), ChangSha, China, 2009. Springer Verlag, LNCS 5532: 241-250 (pdf).
  • A new representation of proper interval graphs with an application to clique-width.
    Pinar Heggernes, Daniel Meister, and Charis Papadopoulos.
    DIMAP Workshop on Algorithmic Graph Theory, (AGT 2009), Warwick, U.K., 2009. Elsevier, ENDM 32: 27-34, 2009.(pdf).
  • Clustering with partial information.
    Hans Bodlaender, Mike Fellows, Pinar Heggernes, Federico Mancini, Charis Papadopoulos, and Fran Rosamond.
    33rd Int'l Symposium on Mathematical Foundations of Computer Science, (MFCS 2008), Torun, Poland, 2008. Springer Verlag, LNCS 5162: 144-155 (pdf).
  • Cutwidth of split graphs, threshold graphs, and proper interval graphs.
    Pinar Heggernes, Daniel Lokshtanov, Rodica Mihai, and Charis Papadopoulos.
    34th Workshop on Graph-Theoretic Concepts in Computer Science, (WG 2008), Durham, U.K., 2008. Springer Verlag LNCS 5344: 218-229 (pdf).
  • Characterizing and computing minimal cograph completions.
    Daniel Lokshtanov, Federico Mancini, and Charis Papadopoulos.
    The Second International Frontiers of Algorithmics Workshop, (FAW 2008), Changsha, China, 2008. Springer Verlag LNCS 5059: 147-158 (pdf).
  • Graphs of linear clique-width at most 3.
    Pinar Heggernes, Daniel Meister, and Charis Papadopoulos.
    5th Annual Conf. on Theory and Applications of Models of Computation, (TAMC 2008), Xi'an, China, 2008. Springer Verlag, LNCS 4978: 330-341 (pdf).
  • Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions.
    Pinar Heggernes and Charis Papadopoulos.
    13th Computing and Combinatorics Conference, (COCOON 2007), Banff, Alberta, Canada, 2007. Springer Verlag, LNCS 4598: 406 - 416 (pdf).
  • Making arbitrary graphs transitively orientable: Minimal comparability completions.
    Pinar Heggernes, Federico Mancini, and Charis Papadopoulos.
    17th Int'l Symposium on Algorithms and Computation, (ISAAC 2006), Kolkata, India, 2006. Springer Verlag, LNCS 4288: 419 - 428 (pdf).
  • A fully dynamic algorithm for the recognition of P4-sparse graphs.
    Stavros D. Nikolopoulos, Leonidas Palios, and Charis Papadopoulos.
    32nd Workshop on Graph-Theoretic Concepts in Computer Science, (WG 2006), Bergen, Norway, 2006. Springer Verlag, LNCS 4271: 256 - 268 (pdf).
  • Drawing graphs using modular decomposition.
    Charis Papadopoulos and Constantinos Voglis.
    13th Int'l Symposium on Graph Drawing, (GD 2005), Limerick, Irelend, 2005. Springer Verlag, LNCS 3843: 343 - 354 (pdf).
  • Optimal algorithms for the path cover problem on P4-sparse graphs.
    Katerina Asdre, Stavros D. Nikolopoulos, and Charis Papadopoulos.
    Cologne-Twente Workshop on Graphs and Combinatorial Optimization , (CTW 2005), Cologne, Germany, 2005. (pdf).
  • The number of spanning trees in P4-reducible graphs.
    Stavros D. Nikolopoulos and Charis Papadopoulos.
    3rd Int'l Colloquium on Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities, (MathInfo III), Birkhauser, Vienna, 2004 (pdf).
  • Counting the number of spanning trees in cographs.
    Stavros D. Nikolopoulos and Charis Papadopoulos.
    Cologne-Twente Workshop on Graphs and Combinatorial Optimization , (CTW 2003), Enschede, The Netherlands, 2003. Elsevier, ENDM 13: 87 - 95, 2003 (pdf).
  • A formula for the number of spanning trees in quasi-threshold graphs.
    Stavros D. Nikolopoulos and Charis Papadopoulos.
    Balcan Conference on Informatics, (BCI 2003), Thessaloniki, Greece, 2003 (pdf).

Technical Reports

Publications