Research Activity -
Algorithms and Complexity

Kristina Vušković

Kristina Vušković's Papers

Publications

• "Combinatorial optimization with 2-joins"
  N. Trotignon and K. Vušković
  submitted to Journal of Combinatorial Theory B , preprint 2009.


• "Chromatic index of graphs with no cycle with a unique chord"
  R.C.S. Machado, C.M.H. de Figueiredo and K. Vušković
  to appear in Theoretical Computer Science , preprint 2009


• "Decomposition of even-hole-free graphs with star cutsets and 2-joins"
  M.V.G. da Silva and K. Vušković
  submitted to Journal of Combinatorial Theory B , preprint 2008.


• "A structure theorem for graphs with no cycle with a unique chord and its consequences"
  N. Trotignon and K. Vušković
  Journal of Graph Theory 63 (1), pages 31-67, 2010.


• "Even-hole-free graphs that do not contain diamonds: a structure theorem and its consequences"
  T. Kloks, H. Muller and K. Vušković
  Journal of Combinatorial Theory B 99 , pages 733-800, 2009.


• "Algorithms for square-3PC(.,.)-free Berge graphs"
  F. Maffray, N. Trotignon and K. Vušković
  SIAM Journal on Discrete Mathematics 22 (1), pages 51-71, 2008.


• "Triangulated neighborhoods in even-hole-free graphs"
  M.V.G. da Silva and K. Vušković
  Discrete Mathematics 307 , pages 1065-1073, 2007.


• "Balanced matrices"
  M. Conforti, G. Cornuéjols and K. Vušković
  Discrete Mathematics 306 , pages 2411-2437, 2006.


• "Odd hole recognition in graphs of bounded clique size"
  M. Conforti, G. Cornuéjols, X. Liu, K. Vušković and G. Zambelli
  SIAM Journal on Discrete Mathematics 20 , No. 1, pages 42-48, 2006.


• "Recognizing Berge graphs"
  M. Chudnovsky, G. Cornuéjols, X. Liu, P. Seymour and K. Vušković
  Combinatorica 25 (2), pages 143-186, 2005.


• "A polynomial algorithm for recognizing perfect graphs"
  G. Cornuéjols, X. Liu and K. Vušković
  Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science , Cambridge, Massacussets, USA, pages 20-27, 2003.


• "Square-free perfect graphs"
  M. Conforti, G. Cornuéjols and K. Vušković
  Journal of Combinatorial Theory B 90 (2), pages 257-307, 2004.


• "Decomposing Berge graphs containing proper wheels"
  M. Conforti, G. Cornuéjols, K. Vušković and G. Zambelli
  preprint (2002).


• "Decomposition of odd-hole-free graphs by double star cutsets and 2-joins"
  M. Conforti, G. Cornuéjols and K. Vušković
  Discrete Applied Mathematics 141 (1-3), pages 41-91, 2004,
  Special issue dedicated to the Brazilian Symposium on Graphs, Algorithms and Combinatorics, Fortaleza, March 17-19, 2001 - Edited by B.A. Reed, S.W. Song and J.L.Szwarcfiter.


• "Even-hole-free graphs, Part I: Decomposition theorem"
  M. Conforti, G. Cornuéjols, A. Kapoor and K. Vušković
  Journal of Graph Theory 39 , pages 6-49, 2002.


• "Even-hole-free graphs, Part II: Recognition algorithm"
  M. Conforti, G. Cornuéjols, A. Kapoor and K. Vušković
  Journal of Graph Theory 40 , pages 238-266, 2002.


• "The graph sandwich problem for 1-join composition is NP-complete"
  C. M. H. de Figueiredo, S. Klein and K. Vušković
  Discrete Applied Mathematics 121 (1-3), pages 73-82, 2002.


• "Perfect graphs, partitionable graphs and cutsets"
  M. Conforti, G. Cornuéjols, G. Gasparyan and K. Vušković
  Combinatorica 22 (1), pages 19-33, 2002.


• "Recognition of quasi-Meyniel graphs"
  C. M. H. de Figueiredo and K. Vušković
  Discrete Applied Mathematics 113 (2-3), pages 255-260, 2001.


• "Balanced 0,+1,-1 matrices, Part I: Decomposition"
  M. Conforti, G. Cornuéjols, A. Kapoor and K. Vušković
  Journal of Combinatorial Theory B 81 (2), pages 243-274, 2001.


• "Balanced 0,+1,-1 matrices, Part II: Recognition algorithm"
  M. Conforti, G. Cornuéjols, A. Kapoor and K. Vušković
  Journal of Combinatorial Theory B 81 (2), pages 275-306, 2001.


• "Triangle-free graphs that are signable without even holes"
  M. Conforti, G. Cornuéjols, A. Kapoor and K. Vušković
  Journal of Graph Theory 34 , pages 204-220, 2000.


• "A class of ß-perfect graphs"
  C. M. H. de Figueiredo and K. Vušković
  Discrete Mathematics 216 , pages 169-193, 2000.


• "Balanced cycles and holes in bipartite graphs"
  M. Conforti, G. Cornuéjols and K. Vušković
  Discrete Mathematics 199 (1-3), pages 27-33, 1999.
  Discrete Mathematics, Editors' Choice 1999.


• "Even and odd holes in cap-free graphs"
  M. Conforti, G. Cornuéjols, A. Kapoor and K. Vušković
  Journal of Graph Theory 30 , pages 289-308, 1999.


• "Perfect, ideal and balanced matrices: A survey"
  M. Conforti, G. Cornuéjols, A. Kapoor and K. Vušković
  Ricerca Operativa 26 (80), pages 65-80, 1997.
  Invited Review, European Journal of Operational Research 133 , pages 455-461, 2001.


• "Universally signable graphs"
  M. Conforti, G. Cornuéjols, A. Kapoor and K. Vušković
  Combinatorica 17 (1), pages 67-77, 1997.


• "Finding an even hole in a graph"
  M. Conforti, G. Cornuéjols, A. Kapoor and K. Vušković
  Proceedings of the $38^{th}$ Annual Conference on Foundations of Computer Science , pages 480-485, 1997.


• "Perfect, Ideal and Balanced Matrices"
  M. Conforti, G. Cornuéjols, A. Kapoor and K. Vušković
  a chapter in Annotated Bibliographies in Combinatorial Optimization edited by M. Dell'Amico, F. Maffioli and S. Martelo; John Wiley and Sons, Ltd., pages 81-94, 1997.


• "Perfect matchings in balanced hypergraphs"
  M. Conforti, G. Cornuéjols, A. Kapoor and K. Vušković
  Combinatorica 16 (3), pages 325-329, 1996.


• "A Mickey-Mouse decomposition theorem"
  M. Conforti, G. Cornuéjols, A. Kapoor and K. Vušković
  Proceedings of the Fourth International Integer Programming and Combinatorial Optimization Conference , Balas and Clausen eds., pages 321-328, Springer Verlag, 1995.


• "Balanced matrices: A survey"
  M. Conforti, G. Cornuéjols, A. Kapoor, M. R. Rao and K. Vušković
  Mathematical Programming: State of the Art 1994 , J. R. Birge and K. G. Murty eds., pages 1-33, The University of Michigan Press, 1994.


• "Recognizing balanced 0,+1,-1 matrices"
  M. Conforti, G. Cornuéjols, A. Kapoor and K. Vušković
  Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 103-111, 1994.