Otimização Discreta e Grafos: Teoria, Algoritmos e Aplicações

Proc. no. 490333/04-4 -- January/2005 to January 2008

Publications of Group G6 (since January 2005)

[Graph Theory: structural, algorithmic and asymptotic problems]
Members: * Jayme L. Szwarcfiter (UFRJ) * Celina M.H. de Figueiredo (UFRJ) * Fábio Protti (UFRJ) * Sulamita Klein (UFRJ) * Márcia R. Ceriolli (UFRJ) * Claudson Ferreira Bornstein (UFRJ) * Luérbio Faria (UERJ - UFRJ) * José Coelho de Pina Jr. (USP) * Yoshiharu Kohayakawa (USP) * Cláudia Linhares Sales (UFC) * Orlando Lee (UNICAMP) * Cláudio Lucchesi (UNICAMP) * Célia Mello (UNICAMP) * Marcos Kiwi (U. de Chile, Chile) * Ivan Rappaport (U. de Chile, Chile) * Martin Matamala (U. de Chile, Chile) * G. Duran (U. de Chile, Chile) * Carmen Ortiz (U. A. Ibañez, Chile) * Monica Villanueva (U. de Santiago, Chile) * Alfredo Viola (U. de la Republica, Uruguay) * Flavia Bonomo (UBA, Argentina) * Min Chih Lin (UBA, Argentina) * Javier Marenco (UBA, Argentina) * Marisa Gutierrez (UNLP, Argentina) * Liliana Alcon (UNLP, Argentina)

Publications in Journals

  1. G. Acosta, S. Guala and J. Marenco, Dynamics of a minority game with an additional layer of interaction, Physica A 387 (2008), 567-572.
  2. L. Alcón, M. R. Cerioli, C. M. H. de Figueiredo, M. Gutierrez and J. Meidanis, Cycles and asteroidal sets in Loop Graphs. Actas de la Academia Nacional de Ciencias, v. XIII, p. 41-49, 2007.
  3. L. Alcón, M. R. Cerioli, C. M. H. de Figueiredo, M. Gutierrez and J. Meidanis, Tree loop graphs, Discrete Appl. Math. 155 (2007), no. 6-7, 686-694.
  4. N. Alon, Y. Kohayakawa, C. Mauduit, C.G. Moreira, and V. Rödl, Measures of pseudorandomness for finite sequences: minimal values, Combinatorics, Probability, and Computing, v. 15, n. 1-2, p. 1-29, 2006.
  5. N. Alon, Y. Kohayakawa, C. Mauduit, C.G. Moreira, and V. Rödl, Measures of pseudorandomness for finite sequences: typical values. Proceedings of the London Mathematical Society, v. 95, p. 778-812, 2007.
  6. B. Bollobas, Y. Kohayakawa, V. Rodl, M. Schacht, A. Taraz, Essentially infinite colourings of hypergraphs, Proceedings of the London Mathematical Society, v. 95, p. 709-734, 2007.
  7. F. Bonomo, Self-clique Helly circular-arc graphs, Discrete Mathematics 306(6) (2006), 595-597.
  8. F. Bonomo, M. Cecowski, Between coloring and list-coloring: µ-coloring, Ars Combinatoria, to appear.
  9. F. Bonomo, M. Chudnovsky and G. Durán, Partial characterizations of clique-perfect graphs I: subclasses of claw-free graphs, Discrete Applied Mathematics, to appear.
  10. F. Bonomo, M. Chudnovsky and G. Durán, Partial characterizations of clique-perfect graphs II: diamond-free and Helly circular-arc graphs, Discrete Mathematics, to appear.
  11. F. Bonomo, G. Durán, M. Lin and J. Szwarcfiter, On Balanced Graphs, Mathematical Programming 105 (2006), 233-250.
  12. F. Bonomo, G. Durán, M. Groshaus and J. Szwarcfiter, On clique-perfect and K-perfect graphs, Ars Combinatoria 80 (2006), 97-112.
  13. F. Bonomo, G. Durán and M. Groshaus, Coordinated graphs and clique graphs of clique-Helly perfect graphs, Utilitas Mathematica, 72 (2007), 175-191.
  14. C. Bornstein, C.M.H. de Figueiredo, V.G.P. de Sá, The pair completion algorithm for the homogeneous set sandwich problem, Inform. Process. Lett. 98 (2006), no. 3, 87--91.
  15. P. Burzyn, F. Bonomo and G. Durán, NP-completeness results for edge modification problems, Discrete Applied Mathematics 154(13) (2006), 1824-1844.
  16. C.N. Campos, C.P. de Mello, A result on the total colouring of powers of cycles, Discrete Appl. Math. 155 (2007), no. 5, 585--597.
  17. R. Carmo, T. Feder, Y. Kohayakawa, E. Laber, R. Motwani, Liadan O'Callaghan, Rina Panigrahy, and Dilys Thomas, Combinatorial Theory (B), 96 (2006), 315-324.
  18. M.H. Carvalho, C.L. Lucchesi and U.S.R. Murty, How to build a brick, Discrete Mathematics, v. 306, p. 2383-2410, 2006.
  19. M.H. Carvalho, C.L. Lucchesi, and U.S.R. Murty, Graphs with independent perfect matchings, Journal of Graph Theory 48 (2005), 19-50.
  20. M. H. Carvalho, C. L. Lucchesi and U. S. R. Murty, On the number of dissimilar Pfaffian orientations of Graphs, Theoretical Informatics and Applications 39 (2005), 93-113.
  21. M.R. Cerioli and J.L. Szwarcfiter, Characterizing Intersection Graphs of Substars of a Stars, Ars Combinatoria, v. 79, p. 21-31, 2006.
  22. M.R. Cerioli, L. Faria, T.O. Ferreira, C.A.J. Martinhon, F. Protti, and B. Reed, Partition into Cliques for Cubic Graphs: Planar Case, Complexity and an Approximation Algorithm. Discrete Applied Mathematics , to appear.
  23. M.R. Cerioli, F.S. Oliveira and J.L. Szwarcfiter, Extreme cliques in interval graphs, Ars Combinatoria, , to appear.
  24. R. Correa adn J.L. Szwarcfiter, Linear Extensions, Upsets and Downsets of Ordered Sets, Discrete Mathematics, v. 295, p. 13-30, 2005.
  25. S. Curran, O. Lee, and X. Yu, Non-separating planar chains in 4-connected graphs, SIAM J. Discr. Math. 19 (2005), 399-419 (electronic).
  26. S. Curran, O. Lee and X. Yu, Chain decompositions of 4-connected graphs, SIAM J. Discr. Math., 19 (2005), 848-880 (electronic).
  27. S. Curran, O. Lee and X. Yu, Finding four independent trees, SIAM J. Comp., SIAM J. Comp. 35 (2006), 1023-1058.
  28. M.D. da Silva, F. Protti, and J.L. Szwarcfiter, Applying Modular Decomposition to Parameterized Cluster Editing Problems, Theory of Computing Systems, to appear.
  29. S. Dantas, C.M.H. de Figueiredo, S. Gravier and S. Klein, Extended skew partition problem, Discrete Math. 306 (2006), no. 19-20, 2438--2449.
  30. C.M.H. de Figueiredo, G. D. da Fonseca, V.G.P. de Sá and J. Spinrad, Algorithms for the homogeneous set sandwich problem, Algorithmica 46 (2006), no. 2, 149--180
  31. C.M.H. de Figueiredo, C.T. Hoàng, F. Maffray, A characterization of $P\sb 4$-comparability graphs, Discrete Math. 306 (2006), no. 19-20, 2461--2472.
  32. C.M.H. de Figueiredo, V.G.P. de Sá, Note on the homogeneous set sandwich problem, Inform. Process. Lett. 93 (2005), no. 2, 75--81.
  33. F.C. Delicato, L. Pirmez, F. Protti, and J. L. Rezende, An Efficient Heuristic for Selecting Active Nodes in Wireless Sensor Networks, Computer Networks, 50, 18 (2006) 3701-3720.
  34. C. De Simone and C.P. de Mello, Edge-colouring of join graphs, Theoretical Computer Science, 355 (2006), 364-370.
  35. S. Dantas, C.M.H. de Figueiredo, S. Gravier and S. Klein, Extended skew partition problem, Discrete Mathematics, > v. 306 (2006), 2438-2449.
  36. C.P. de Mello, A. Morgana and M. Liverani, The clique operator on graphs with few $P\sb 4$'s, Discrete Appl. Math. 154 (2006), no. 3, 485--492.
  37. V.M.F. Dias, C.M.H. de Figueiredo and J.L. Szwarcfiter, Generating Bicliques of a Graph in Lexicographic Order, Theoretical Computer Science, v. 37, p. 240-248, 2005.
  38. V.M.F. Dias, C.M.H. de Figueiredo and J.L. Szwarcfiter, On the generation of bicliques of a graph, Discrete Applied Mathematics, v. 155, p. 1826-1832, 2007.
  39. P. Dobson, M. Gutierrez, M. Habib and J.L. Szwarcfiter, On transitive orientations with restricted covering graphs, Information Processing Letters, v. 101, p. 119-125, 2007.
  40. P. Dobson, M. Gutierrez, M. Habib and J.L. Szwarcfiter, Characterizations of Treelike Comparability Graphs, Congressus Numerantium, v. 182, p. 23-32, 2006.
  41. J. Donadelli, P.E. Haxell, and Y. Kohayakawa, A note on the size-Ramsey number of long subdivisions of graphs, Theoretical Informatics and Applications, 39 (2005), no. 1, 191-206.
  42. M.C. Dourado, J.G. Gimbel, F. Protti, and J.L. Szwarcfiter, On the Computation of the Hull Number of a Graph, Discrete Mathematics, to appear.
  43. M.C. Dourado, F. Protti, and J.L. Szwarcfiter, Computational Aspects of the Helly Property: a Survey, Journal of the Brazilian Computer Society, 12,1 (2006) 7-33.
  44. M.C. Dourado, F. Protti and J.L. Szwarcfiter, On the strong p-Helly property, Discrete Applied Mathematics,, to appear.
  45. M.C. Dourado, F. Protti, and J.L. Szwarcfiter, The Helly property on subfamilies of limited size, Information Processing Letters 93,2 (2005) 53-56.
  46. M.C. Dourado, F. Protti, and J.L. Szwarcfiter, Complexity Aspects of Generalized Helly Hypergraphs, Information Processing Letters 99 (2006) 13-18.
  47. M.C. Dourado, F. Protti and J.L. Szwarcfiter, Characterization and recognition of generalized clique-Helly graphs, Discrete Applied Mathematics, v. 155, p. 2435-2443, 2007.
  48. G. Durán, A. Gravano, R. McConnell, J. Spinrad and A. Tucker, Polynomial time recognition of unit circular-arc graphs, Journal of Algorithms 58 (2006), 67-78.
  49. G. Durán, M. Lin, S. Mera and J.L. Szwarcfiter, Algorithms for clique-independent sets on subclasses of circular-arc graphs, Discrete Applied Mathematics 154(13) (2006), 1783-1790.
  50. G. Duran, M.C. Lin, S. Mera and J.L. Szwarcfiter, Algorithms for finding clique transversals of graphs, Annals of Operations Research, v. 157 (1) (2008), 37-45.
  51. N. Eaton, Z. Füredi, A. Kostochka, J. Skokan, Tree representations of graphs, European Journal of Combinatorics 22(4), 2007, 1087-1098. [Skokan: posdoc]
  52. H. Everett, C.M.H. de Figueiredo, S. Klein and B. Reed, The perfection and recognition of bull-reducible Berge graphs. Theor. Inform. Appl. 39 (2005), no. 1, 145--160.
  53. M. H. C. Fampa, S. Klein, F. Protti, and D.C.A. Rêgo, Optimal Grid Representations, Networks 44 (2004) 187-193.
  54. L. Faria, C.M.H. de Figueiredo, S. Gravier, C.F.X. Mendonça, J. Stolfi, On maximum planar induced subgraphs, Discrete Appl. Math. 154 (2006), no. 13, 1774--1782.
  55. L. Faria, C.M.H. Figueiredo, S. Klein and R. Sritharan, On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs, Theoretical Computer Science, v. 381 (2007), 57-67.
  56. M. Ferrara, Y. Kohayakawa, and V.Rödl, Distance graphs on the integers, Combinatorics, Probability, and Computing 14 (2005), no. 1-2, 107-131.
  57. Shinya Fujita, Ken-ichi Kawarabayashi, Claudio Leonardo Lucchesi, Katsuhiro Ota, Michael D. Plummer and Akira Saito. A pair of forbidden subgraphs and perfect matchings, Journal of Combinatorial Theory (B), 96 (2006), 315-324.
  58. S. Gerke, Y. Kohayakawa, V. Rödl, and A. Steger, Small subsets inherit sparse \epsilon-regularity, Journal of Combinatorial Theory Series B, v. 97, p. 34-56, 2007.
  59. M. Groshaus and J.L. Szwarcfiter, Biclique-Helly graphs, Graphs and Combinatorics, , to appear.
  60. M. Groshaus and J.L. Szwarcfiter, On hereditary Helly classes of graphs, Discrete Mathematics and Theoretical Computer Science (Online), to appear.
  61. P.E. Haxell, T. Luczak, Y. Peng, V. Rödl, A. Rucinski, M. Simonovits, J. Skokan, The Ramsey number for hypergraph cycles I., J. Combin. Theory Ser. A 113(1), 2006, pp. 67-83. [Skokan: posdoc]
  62. P. Hell, S. Klein, L.T. Nogueira, and F. Protti, List Matrix Partitions of Chordal Graphs, Theoretical Computer Science 349 (2005) 52-66.
  63. P. Hell, S. Klein, L.T. Nogueira, and F. Protti, Partitioning Chordal Graphs into Independent Sets and Cliques,  Discrete Applied Mathematics141 (2004) 185-194.
  64. P. Hell, S. Klein, L.T. Nogueira, and F. Protti, Packing r-cliques in Weighted Chordal Graphs, Annals of Operations Research 138 (2005) 179-187.
  65. K. Kawarabayashi, O. Lee, and X. Yu, Non-separating paths with prescribed ends in 4-connected graphs, Annals of Combinatorics 9 (2005), 47-56.
  66. S.J. Kim, K. Nakprasit, M. Pelsmajer, J. Skokan, Transversal numbers of translates of a convex body, Discrete Mathematics 306 (18), 2006, 2166-2173. [Skokan: posdoc]
  67. S. Klein, H. Everett, C.M.H. de Figueiredo and B. Reed, The perfection and recognition of bull-reducible Berge graphs, RAIRO - Informatique Théorique et Applications, França, v. 39 (2005), 145-160.
  68. S. Klein, C.M.H. de Figueiredo, S. Dantas, S. Gravier, Finding H-partitions efficiently, RAIRO - Informatique Théorique et Applications, França, v. 39 (2005), 133-144.
  69. S. Klein, P. Hell, L.T. Nogueira and F. Protti, Packing r-cliques in weighted chordal graphs, Annals of Operational Research, Netherlands, v. 138 (2005), 179-187.
  70. S. Klein, T. Feder, P. Hell, L.T. Nogueira and F. Protti, List Partitions of Chordal Graphs, Theoretical Computer Science, v. 349 (2005), 52-66.
  71. Y. Kohayakawa, V. Rödl, M. Schacht, P. Sissokho, J. Skokan, Turán's Theorem for pseudorandom graphs, J. Combin. Th. Series A 114(4), 2007, pp. 631-657.
  72. L.A.B. Kowada, R. Portugal and C.M.H. de Figueiredo, Reversible Karatsuba's algorithm, J. UCS 12 (2006), no. 5, 499--511 (electronic).
  73. M.C. Lin and J.L. Szwarcfiter, Unit circular-arc graph representations and feasible circulations, SIAM Journal on Discrete Mathematics, to appear.
  74. M.C. Lin and J.L. Szwarcfiter, Faster recognition of clique-Helly and hereditary clique-Helly graphs, Information Processing Letters, v. 103, p. 40-43, 2007.
  75. M. Liverani, A. Morgana, C.P. de Mello,The $K$-behaviour of $p$-trees. Ars Combin. 83 (2007), 33--45.
  76. M. Matamala, Vertex partitions and maximum degenerate subgraphs, , v. 55 (2007), Issue 3, 227-232.
  77. Y. Peng, V. Rödl, J. Skokan, Counting small cliques in 3-uniform hypergraphs, Combinatorics, Probability, Computing, 14(3), 2005, 371-413. [Skokan: posdoc]
  78. P.E.D. Pinto, F. Protti, and J. L. Szwarcfiter, Parity Codes, RAIRO-Theoretical Informatics and Applications 39 (2005) 263-278.
  79. F. Protti and J.L. Szwarcfiter, On the complexity of the geodetic and convexity numbers of a graph, Lecture Notes of the Ramanujan Mathematical Society, to appear.
  80. V. Rödl, B. Nagle, J. Skokan, M. Schacht, and Y. Kohayakawa, The hypergraph regularity method and its applications, Proceedings of the National Academy of Sciences (USA), 102 (23), 2005, 8109-8113.
  81. M.J. Stein, Arboricity and tree-packing in locally finite graphs, J. Combin. Theory Ser. B 96 (2006), no. 2, 302-312. [Stein: posdoc]
  82. M.J. Stein, Forcing highly connected subgraphs. J. Graph Theory 54 (2007), no. 4, 331-349. [Stein: posdoc]
  83. R.B. Teixeira and C.M.H. de Figueiredo, The sandwich problem for cutsets: clique cutset, k-star cutset, Discrete Appl. Math. 154 (2006), no. 13, 1791--1798.

Publications in International Conference Proceedings

  1. A. Abouelaoualim and K. Ch. Das and L. Faria and Y. Manoussakis and C. Martinhon and R. Saad, Paths and Trails in Edge-Colored Graphs, Proceedings of the 8th Latin American Theoretical Informatics Symposium (LATINÇ2008), Lecture Notres in Computer Science to appear.
  2. L. Alcón, M.R. Cerioli, C.M.H. de Figueiredo, M. Gutierrez and J. Meidanis, Non Loop Graphs with induced Cycles, Proceedings of the Second Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO 2005), Electronic Notes in Discrete Mathematics 19, 2005, 179-183.
  3. L. Alcón, M.R. Cerioli, C.M.H. de Figueiredo, M. Gutierrez and J. Meidanis, Loop Graphs with Asteroidals Sets, Proceedings of the 7th International Colloquium on Graph Theory (ICGT’05), Electronic Notes in Discrete Mathematics 22, 2005, 289-295.
  4. L. Alcón, L. Farias, C.M.H. de Figueiredo, M. Gutierrez, Clique Graph recognition is NP-Complete, Proceedings of the 32th International Workshop on Graph Theory Concepts in Computer Science (WG’06), Lecture Notes in Computer Science to appear.
  5. L. Alcón, L. Faria, C.M..H. de Figueiredo and M. Gutierrez, On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs, Proceedings of IV Latin-American Algorithms, Graphs and Optimization Symposium, (LAGOS 2007), Electronic Notes in Discrete Mathematics to appear.
  6. J. Barrionuevo, A. Calvo, G. Durán and F. Protti, New advances about a conjecture on Helly circle graphs, Proceedings of the Latin American Conference on Combinatorics, Graphs and Applications (LACGA 2004), Electronic Notes in Discrete Mathematics 18 (2004), 31-36.
  7. F. Bonomo and M. Cecowski, Between coloring and list-coloring: mu-coloring, Proceedings of the Second Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO 2005), Electronic Notes in Discrete Mathematics 19, 2005, 117-123.
  8. F. Bonomo, M. Chudnovsky and G. Durán, Partial characterizations of clique-perfect graphs, Proceedings of the Second Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO 2005), Electronic Notes in Discrete Mathematics 19 (2005), 95-101.
  9. F. Bonomo and G. Durán, Characterization and recognition of Helly circular-arc clique-perfect graphs, Proceedings of the 7th International Colloquium on Graph Theory (ICGT 2005), Electronic Notes in Discrete Mathematics 22 (2005), 147-150.
  10. F. Bonomo, G. Durán, L.N. Grippo and M.D. Safe, Partial characterizations of circular-arc graphs, Proceedings of the IV Latin-American Graphs and Optimization Symposium (LAGOS 2007), Electronic Notes in Discrete Mathematics 30 (2008), 45-50.
  11. F. Bonomo, G. Durán and J. Marenco, Exploring the complexity boundary between coloring and list-coloring, Proceedings of the Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2006), Electronic Notes in Discrete Mathematics (2006).
  12. F. Bonomo, G. Durán, F. Soulignac and G. Sueiro, Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs, Proceedings of the IV Latin-American Graphs and Optimization Symposium (LAGOS 2007), Electronic Notes in Discrete Mathematics 30 (2008), 51-56.
  13. C.F. Bornstein, E.S. Laber and M.A.F. Más, Randomized mechanisms for limited supply multi-item auctions, Proceedings of the Second Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO 2005), Electronic Notes in Discrete Mathematics 19 (2005), 141-147.
  14. F.C. Botelho, Y. Kohayakawa, and N. Ziviani, A practical minimal perfect hashing method, Proceedings of the fourth International Workshop on Experimental and Efficient Algorithms (WEA 2005), Santorini Island, Greece (S.E. Nikoletseas, ed.), Lecture Notes in Computer Science, vol. 3503, Springer, 2005, 488-500. Computer Science, vol. 3059 (2004), pp. 175-190.
  15. P. Burzyn, F. Bonomo and G. Durán., Computational complexity of edge modification problems in different classes of graphs, Proceedings of the Latin American Conference on Combinatorics, Graphs and Applications (LACGA 2004), Electronic Notes in Discrete Mathematics 18 (2004), 41-46.
  16. D. Carvalho, F.M.G. França, and F. Protti, A Novel Distributed Scheduling Algorithm for Resource Sharing under Near-heavy Load, OPODIS 2004 - 8th Conference on Principles of Distributed Systems. Grenoble, France, december 2004. Lecture Notes in Computer Science 3544 (2004). 
  17. M.R. Cerioli, L. Faria, T.O. Ferreira, and F. Protti, On Minimum Clique Partition and Maximum Independent Set in Unit Disk Graphs and Penny Graphs: Complexity and Approximation, LACGA'2004 - Latin-American Conference on Combinatorics, Graphs and Applications. Santiago, Chile, august 2004. Eletronic Notes in Discrete Mathematics, Vol. 18, Elsevier.
  18. M.R. Cerioli and P.C. Petito. Forbidden subgraph characterization of split graphs that are UEH. Proceedings of the Brazilian Symposium on Graphs, Algorithms and Combinatorics, (GRACO 2005), Electronic Notes in Discrete Mathematics, 19 (2005) 305-311.
  19. M.R. Cerioli, F.S. Oliveira, and J.L. Szwarcfiter. Linear-interval dimension and PI orders. Proceedings of the Latin-American Algorithms, Graphs and Optimization Symposium, (LAGOS 2007), Electronic Notes in Discrete Mathematics, to appear.
  20. M.R. Cerioli and P.C. Petito. Clique-coloring UE and UEH graphs. Proceedings of the Latin-American Algorithms, Graphs and Optimization Symposium, (LAGOS 2007), Electronic Notes in Discrete Mathematics, to appear.
  21. C.M.H. de Figueiredo, F. Maffray, M. Villela and R. Claudia, Even pairs in bull-reducible graphs. Graph theory in Paris, 179--195, Trends Math., Birkhäuser, Basel, 2007.
  22. S. D. de Souza, and L. Faria, L., On Stubborn sandwich problems, Proceedings of the International Multi-Conference on Computing in the Global Information Technology (ICCGI'2007), IEEE Computer Society (2007), 46-52.
  23. D. Dellamonica Jr. and Y. Kohayakawa, An algorithmic Friedman-Pippenger theorem on tree embeddings and applications to routing (extended abstract), Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006. p. 1038-1044.
  24. D. Dellamonica Jr, Y. Kohayakawa, V. Rodl and A> Rucinski, Universality of random graphs, Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms, (SODA), 2008, to appear.
  25. F. C. Delicato, L. Pirmez, F. Protti, J. F. Rezende, and L. Rust, Aplication-Driven Node Management in Multihop Wireless Sensor Networks, ICN 2005 - 4th International Conference on Networking. Reunion Island, april 2005, Lecture Notes in Computer Science 3420 (2005) 569-576.
  26. M.C. Dourado, F. Protti, and J.L. Szwarcfiter, The Helly Property on Subhypergraphs, GRACO'2005 - Brazilian Symposium on Graphs, Algorithms and Combinatorics, Angra dos Reis, Brazil, april 2005. Eletronic Notes in Discrete Mathematics 19 (2005) 71-77.
  27. M.C. Dourado, F. Protti and J.L. Szwarcfiter, Algorithmic Aspects of Monophonic Convexity, LAGOS'07 - IV Latin-American Graphs, Algorithms and Optimization Symposium, Puerto Varas, Chile,november 2007, Eletronic Notes in Discrete Mathematics, to appear.
  28. M.C. Dourado, F. Protti, and J.L. Szwarcfiter, On the Computation of some Parameters Related to Convexity of Graphs, ICDM 2006 - International Conference on Discrete Mathematics, Bangalore, India, december 2006, Proceedings, pp. 102-112.
  29. G. Durán, M. Lin, S. Mera and J.L. Szwarcfiter, Clique-independent sets of Helly circular-arc graphs, Proceedings of the Latin American Conference on Combinatorics, Graphs and Applications (LACGA 2004), Electronic Notes in Discrete Mathematics 18 (2004), 103-108.
  30. G. Durán, M. Lin, S. Mera and J.L. Szwarcfiter, Algorithms for finding clique-transversals of graphs, accepted to Annals of Operations Research.
  31. L. Faria, A. R. de Lyra and C. A. de J. Martinhon, On the 3SAT instance expected optimum value. Proceedings of the 38th Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Southeastern International Conference on Combinatorics, Graph Theory, and Computing, 2007.
  32. A. L. P. Guedes, L. Markenzon and L. FARIA, Flow hypergraph reducibility. Proceedings of IV Latin-American Algorithms, Graphs and Optimization Symposium, (LAGOS 2007), Electronic Notes in Discrete Mathematics, to appear.
  33. M. Gutierrez, S. Tondato and J.L. Szwarcfiter , A forbidden subgraph characterization of path graphs, Proceedings of the Second Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO 2005), Electronic Notes in Discrete Mathematics 19, 2005, 281-287.
  34. M. Gutierrez, J. L. Szwaecfiter and S. Tondato, Clique trees of chordal graphs: leafage and 3-asteroidal, Proceedings of IV Latin-American Algorithms, Graphs and Optimization Symposium, (LAGOS 2007), Electronic Notes in Discrete Mathematics to appear.
  35. M. Kiwi, A concentration bound for the longest increasing subsequence of a randomly chosen involution, Discrete Appl. Math. 154 (2006), no. 13, 1816-1823.
  36. M. Kiwi, M. Loebl and J. Matousek, Expected length of the longest common subsequence for large alphabets, Adv. Math. 197 (2005), no. 2, 480-498.
  37. S. Klein, S. Dantas, C.P. de Mello and A. Morgana, The P4-sparse Graph Sandwich Problem. In: 7th International Colloquium on Graph Theory, 2005, Hyeres-França, Electronic Notes in Discrete Mathematics, v. 22 (2005), 185-188.
  38. S. Klein, R.S. Francisco and L.T. Nogueira, Characterizing (k,l)-partitionable Cographs. In: 7th International Colloquium on Graph Theory, 2005, Hyeres-França, Electronic Notes in Discrete Mathematics, v. 22 (2005), 277-280.
  39. S. Klein, N.C. dos Santos and J.L. Szwarcfiter, A representation for the modular-pairs of a P4-reducible graph. In: 7th International Colloquium on Graph Theory, 2005, Hyeres-França, Electronic Notes in Discrete Mathematics, v. 22 (2005), 267-270.
  40. Y. Kohayakawa, M. Simonovits, and J. Skokan, The 3-colored Ramsey number of odd cycles, Proceedings of the Second Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO 2005), Electronic Notes in Discrete Mathematics 19 (2005), 397-402.
  41. E. Moreno and M. Matamala, Minimal Eulerian circuit in a labeled digraph, LATIN 2006, Lecture Notes in Computer Science , v. 3887 (2006), 737-744.
  42. O. Lee and A. Williams, Packing dicycle covers in planar graphs with no K_5-e minor. Proceedings of the 7th Latin American Theoretical Informatics Symposium (LATIN'06), Valdivia, Chile. Lecture Notes in Comp. Science 3887 (2006), 677-688.
  43. M. Lin, R. McConnell, F. Soulignac and J.L. Szwarcfiter, On cliques of Helly circular-arc graphs. Proceedings of IV Latin-American Algorithms, Graphs and Optimization Symposium, (LAGOS 2007), Electronic Notes in Discrete Mathematics, to appear.
  44. M. Lin, F. Soulignac and J.L. Szwarcfiter, Proper Helly Circular-Arc Graphs. Proceedings of the 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG'07), Dornburg, Germany, Lecture Notes in Computer Science 4769 (2007), 248-257.
  45. M. Lin and J.L. Szwarcfiter, Efficient Construction of Unit Circular-Arc Models. Proceedings of the 17th annual ACM-SIAM symposium on Discrete algorithm (SODA'06), Miami, EEUU, (2006), 309-315.
  46. M. Lin and J. Szwarcfiter, Characterizations and linear time recognition of helly circular-arc graphs. Proceedings of the 12th Annual International Computing and Combinatorics Conference (COCOON'06), Taipei, Taiwan, Lecture Notes in Computer Sciences 4112 (2006), 73-82.
  47. M. Lin and J.L. Szwarcfiter, Linear Time Recognition and Representation of Unit Circular-Arc Graphs, SIAM Journal on Discrete Mathematics, to appear.
  48. M. Matamala and J. Zamora, A new family of K-divergent graphs, Proceedings of the Second Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO 2005), Electronic Notes in Discrete Mathematics 19 (2005), 357-363
  49. A. Miranda and C.L. Lucchesi, A Polynomial Time Algorithm for Recognizing Near-Bipartite Pfaffian Graphs. In: IV Latin-American Algorithms, Graphs and Algorithms (LAGOS 2007), Electronic Notes in Discrete Mathematics, to appear.
  50. F. Protti, M.D. da Silva, and J.L.Szwarcfiter, Applying Modular Decomposition to Parameterized Bicluster Editing, IWPEC 2006 - The Second International Workshop on Parameterized and Exact Computation, Zürich, Switzerland, september 2006, Lecture Notes in Computer Science 4169 (2006) 1-12.
  51. C.N. Silva and C.L. Lucchesi, Flow Critical Graphs. In: IV Latin-American Algorithms, Graphs and Algorithms (LAGOS 2007), Electronic Notes in Discrete Mathematics, to appear.

Editorial Work

  1. J.R. Correa, A. Hevia and Marcos Kiwi (eds). LATIN 2006: Theoretical informatics. Proceedings of the 7th Latin American Symposium held in Valdivia, March 20--24, 2006. Lecture Notes in Computer Science, 3887. Springer-Verlag, Berlin, 2006. xvi+814.
  2. G. Durán, T. Liebling and M. Matamala, Traces of the Latin American Conference on Combinatorics, Graphs and Applications: A selection of papers from LACGA 2004, Santiago, Chile. Discrete Applied Mathematics, (Elsevier Science Publishers) 154(13), 1771-1772, 2006.
  3. P. Feofiloff, C.M.H. de Figueiredo and Y. Wakabayashi (editors) Preface[ Proceedings of the Second Brazilian Symposium on Graphs, Algorithms and Combinatorics]. Electronic Notes in Discrete Mathematics, (Elsevier Science Publishers) 19, 1-7, 2005.
  4. Th. Liebling, J.L. Szwarcfiter, G. Durán and M. Matamala (editors) Preface [Proceedings of the IV Latin-American Graphs and Optimization Symposium]. Electronic Notes in Discrete Mathematics, (Elsevier Science Publishers) 30, 1-2, 2008.

Submitted Manuscripts

  1. L. Álcon, L. Faria, C. M. H. de Figueiredo, M. Gutierrez, The complexity of clique graph recognition.
  2. M. Barros, P. Lima, F. Protti e E. Schmitz, Automated Transformation of XML Instances.
  3. F. Bonomo and M. Cecowski, Between coloring and list-coloring: mu-coloring, Ars Combinatoria (2006).
  4. F. Bonomo, G. Durán, L.N. Grippo and M.D. Safe, Partial characterizations of circular-arc graphs, Journal of Graph Theory.
  5. F. Bonomo, G. Durán and J. Marenco, Exploring the complexity boundary between coloring and list-coloring, Annals of Operations Research.
  6. F. Bonomo G. Durán, F. Soulignac and G. Sueiro, Partial characterizations of coordinated graphs: line graphs and complements of forests, Mathematical Methods of Operations Research.
  7. F. Bonomo G. Durán, F. Soulignac and G. Sueiro, Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs, Discrete Applied Mathematics.
  8. S. Dantas, E. Eschen, L. Faria, C. M. H. de Figueiredo and S. Klein, 2K2 vertex-set partition into nonemptyparts.
  9. C. M. H. de Figueiredo, M. C. Dourado, P. Petito, R. B. Teixeira, Helly property, clique graphs, complementary graph classes, and sandwich problems.
  10. C. M. H. de Figueiredo and R. Machado, On breadth first search and graph diameter bounds.
  11. C. M. H. de Figueiredo, L. A. B. Kowada, C. Lavor and R. Portugal, A new quantum algorithm to solve the minimum searching problem.
  12. M.C. Dourado, F. Protti e J.L. Szwarcfiter, On Helly Hypergraphs with Predescribed Intersection Sizes.
  13. L. Faria, C. M. H. de Figueiredo, O. Sýkora and I. Vrto, An improved upper bound on the crossing number of the hypercube.
  14. K. Kawarabayashi, B. Reed and O. Lee, Removable cycles in nonbipartite graphs.
  15. M. Lin and J.L. Szwarcfiter, Characterizations and recognition of circular-arc graphs and subclasses: a survey, Discrete Mathematics.
  16. P.E.D. Pinto, F. Protti e J.L. Szwarcfiter, Exact and Experimental Algorithms for a Huffman-based Error Detecting Code.
Y. Wakabayashi <yw@ime.usp.br>
Last modified: Tue Feb 26 12:39:56 BRT 2008