\n \n \n
\n
\n\n \n \n \n \n \n \n The Chromatic Index of Proper Circular-arc Graphs of Odd Maximum Degree which are Chordal.\n \n \n \n \n\n\n \n João Pedro W. Bernardi; Murilo V. G. Silva; André Luiz P. Guedes; and Leandro M. Zatesko.\n\n\n \n\n\n\n
Electronic Notes in Theoretical Computer Science, 346: 125-133. 2019.\n
The proceedings of Lagos 2019, the tenth Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS 2019)\n\n
\n\n
\n\n
\n\n \n \n
Paper\n \n \n\n \n \n doi\n \n \n\n \n link\n \n \n\n bibtex\n \n\n \n \n \n abstract \n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n \n \n \n \n \n \n \n \n \n \n\n\n\n
\n
@Article{Bernardi2019,\n title = {The Chromatic Index of Proper Circular-arc Graphs of\n Odd Maximum Degree which are Chordal},\n journal = {Electronic Notes in Theoretical Computer Science},\n volume = {346},\n pages = {125-133},\n year = {2019},\n note = {The proceedings of Lagos 2019, the tenth Latin and\n American Algorithms, Graphs and Optimization Symposium\n (LAGOS 2019)},\n _keywords = {Universal2016},\n organization = {UFMG},\n issn = {1571-0661},\n doi = {https://doi.org/10.1016/j.entcs.2019.08.012},\n url =\n {http://www.sciencedirect.com/science/article/pii/S1571066119300623},\n author = {João Pedro W. Bernardi and Murilo V. G. da Silva and\n André Luiz P. Guedes and Leandro M. Zatesko},\n keywords = {Pullback, circular-arc, chromatic index,\n edge-coloring, chordal},\n abstract = {The complexity of the edge-coloring problem when\n restricted to chordal graphs, listed in the famous\n D. Johnson's NP-completeness column of 1985, is still\n undetermined. A conjecture of Figueiredo, Meidanis,\n and Mello, open since the late 1990s, states that all\n chordal graphs of odd maximum degree Δ have chromatic\n index equal to Δ. This conjecture has already been\n proved for proper interval graphs (a subclass of\n proper circular-arc ∩ chordal graphs) of odd Δ by a\n technique called pullback. Using a new technique\n called multi-pullback, we show that this conjecture\n holds for all proper circular-arc ∩ chordal graphs of\n odd Δ. We also believe that this technique can be used\n for further results on edge-coloring other graph\n classes.}\n}\n\n
\n
\n\n\n
\n The complexity of the edge-coloring problem when restricted to chordal graphs, listed in the famous D. Johnson's NP-completeness column of 1985, is still undetermined. A conjecture of Figueiredo, Meidanis, and Mello, open since the late 1990s, states that all chordal graphs of odd maximum degree Δ have chromatic index equal to Δ. This conjecture has already been proved for proper interval graphs (a subclass of proper circular-arc ∩ chordal graphs) of odd Δ by a technique called pullback. Using a new technique called multi-pullback, we show that this conjecture holds for all proper circular-arc ∩ chordal graphs of odd Δ. We also believe that this technique can be used for further results on edge-coloring other graph classes.\n
\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n Subclasses of Circular-Arc Bigraphs: Helly, Normal and Proper.\n \n \n \n \n\n\n \n Marina Groshaus; André L.P. Guedes; and Fabricio Schiavon Kolberg.\n\n\n \n\n\n\n
Electronic Notes in Theoretical Computer Science, 346: 497-509. 2019.\n
The proceedings of Lagos 2019, the tenth Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS 2019)\n\n
\n\n
\n\n
\n\n \n \n
Paper\n \n \n\n \n \n doi\n \n \n\n \n link\n \n \n\n bibtex\n \n\n \n \n \n abstract \n \n\n \n \n \n 1 download\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n\n\n\n
\n
@Article{Kolberg2019,\n title = {Subclasses of Circular-Arc Bigraphs: Helly, Normal\n and Proper},\n journal = {Electronic Notes in Theoretical Computer Science},\n volume = {346},\n pages = {497-509},\n year = {2019},\n note = {The proceedings of Lagos 2019, the tenth Latin and\n American Algorithms, Graphs and Optimization Symposium\n (LAGOS 2019)},\n _keywords = {Universal2016},\n organization = {UFMG},\n issn = {1571-0661},\n doi = {https://doi.org/10.1016/j.entcs.2019.08.044},\n url =\n {http://www.sciencedirect.com/science/article/pii/S1571066119300957},\n author = {Marina Groshaus and André L.P. Guedes and Fabricio\n Schiavon Kolberg},\n keywords = {Biclique, Circular-arc, recognition, Helly, Normal,\n Proper},\n abstract = {The class of circular-arc graphs, as well as its\n Helly, normal, and proper subclasses, has been\n extensively studied in the literature. Circular-arc\n bigraphs, a bipartite variation on circular-arc\n graphs, remains a relatively new field, with only a\n few studies on the class and its proper and unit\n subclasses existing. In this paper, we introduce a\n Helly subclass for circular-arc bigraphs, based on the\n concept of bipartite-Helly families, and provide a\n polynomial-time recognition algorithm for it. We also\n introduce an alternative proper circular-arc bigraph\n subclass to the one in the literature, as well as two\n different normal circular-arc bigraph subclasses based\n on the definition of normal circular-arc graphs. We\n present containment relations between the different\n proper and normal classes.}\n}\n\n
\n
\n\n\n
\n The class of circular-arc graphs, as well as its Helly, normal, and proper subclasses, has been extensively studied in the literature. Circular-arc bigraphs, a bipartite variation on circular-arc graphs, remains a relatively new field, with only a few studies on the class and its proper and unit subclasses existing. In this paper, we introduce a Helly subclass for circular-arc bigraphs, based on the concept of bipartite-Helly families, and provide a polynomial-time recognition algorithm for it. We also introduce an alternative proper circular-arc bigraph subclass to the one in the literature, as well as two different normal circular-arc bigraph subclasses based on the definition of normal circular-arc graphs. We present containment relations between the different proper and normal classes.\n
\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n On the chromatic index of complementary prisms.\n \n \n \n \n\n\n \n Leandro Zatesko; Renato Carmo; André Guedes; Alesom Zorzi; Raphael Machado; and Celina Figueiredo.\n\n\n \n\n\n\n
Acta Mathematica Universitatis Comenianae, 88(3): 1071-1077. 2019.\n
EUROCOMB'2019\n\n
\n\n
\n\n
\n\n \n \n
Paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n \n \n abstract \n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@Article{ZCGZMF2019,\n author = {Leandro Zatesko and Renato Carmo and André Guedes and\n Alesom Zorzi and Raphael Machado and Celina\n Figueiredo},\n title = {On the chromatic index of complementary prisms},\n journal = {Acta Mathematica Universitatis Comenianae},\n volume = {88},\n number = {3},\n year = {2019},\n _keywords = {Universal2016},\n abstract = {This paper addresses the edge-colouring problem\n restricted to the graph class of complementary\n prisms. This graph class includes the Petersen graph,\n a very important and widely studied graph in the\n context of graph edge-colouring and remarkable related\n open questions, such as the Overfull Conjecture. We\n prove that all non-regular complementary prisms are\n Class 1 and we conjecture that the only Class 2\n regular complementary prism is the Petersen graph. We\n present evidences for this conjecture.},\n issn = {0862-9544},\n pages = {1071-1077},\n url =\n {http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1208},\n note = {EUROCOMB'2019}\n}\n\n
\n
\n\n\n
\n This paper addresses the edge-colouring problem restricted to the graph class of complementary prisms. This graph class includes the Petersen graph, a very important and widely studied graph in the context of graph edge-colouring and remarkable related open questions, such as the Overfull Conjecture. We prove that all non-regular complementary prisms are Class 1 and we conjecture that the only Class 2 regular complementary prism is the Petersen graph. We present evidences for this conjecture.\n
\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n A Connectivity-based Decomposition for Graph Edge-colouring.\n \n \n \n \n\n\n \n Leandro Zatesko; João P. W. Bernardi; Sheila M. Almeida; Renato Carmo; and André L. P. Guedes.\n\n\n \n\n\n\n
Matemática Contemporânea, 46: 156-164. 2019.\n
2018 – 8th Latin-American Workshop on Cliques in Graphs\n\n
\n\n
\n\n
\n\n \n \n
Paper\n \n \n \n
pdf\n \n \n\n \n \n doi\n \n \n\n \n link\n \n \n\n bibtex\n \n\n \n \n \n abstract \n \n\n \n \n \n 3 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@Article{ZateskoBernardiAlmeidaCarmoGuedes2019,\n author = {Leandro Zatesko and João P. W. Bernardi and Sheila\n M. de Almeida and Renato Carmo and André L. P. Guedes},\n title = {A Connectivity-based Decomposition for Graph\n Edge-colouring},\n journal = {Matemática Contemporânea},\n issn = {2317-6636},\n volume = {46},\n year = {2019},\n abstract = {We show how the problem of computing an optimal\n edge-colouring of a graph G can be decomposed into the\n problem of computing optimal edge-colourings of the\n biconnected components of G. That is, once optimal\n edge-colourings of the biconnected components are\n independently given, they can be adjusted in\n polynomial time in order to compose an optimal\n edge-colouring of the whole graph G with no colour\n conflicts. We use this decomposition strategy to show\n that a long-standing conjecture (proposed by\n Figueiredo, Meidanis, and Mello in mid-1990s) on\n edge-colouring chordal graphs of odd maximum degree ∆\n holds when ∆ = 3. We discuss further decomposition\n algorithms for graph edge-colouring.},\n publisher = {Sociedade Brasileira de Matemática},\n pages = {156-164},\n doi = {http://doi.org/10.21711/231766362020/rmc4616},\n _keywords = {Universal2016},\n url = {https://mc.sbm.org.br/volumes/volume-46/},\n url_pdf =\n {https://mc.sbm.org.br/wp-content/uploads/sites/15/2019/12/P16.pdf},\n note = {2018 – 8th Latin-American Workshop on Cliques in\n Graphs}\n}\n\n
\n
\n\n\n
\n We show how the problem of computing an optimal edge-colouring of a graph G can be decomposed into the problem of computing optimal edge-colourings of the biconnected components of G. That is, once optimal edge-colourings of the biconnected components are independently given, they can be adjusted in polynomial time in order to compose an optimal edge-colouring of the whole graph G with no colour conflicts. We use this decomposition strategy to show that a long-standing conjecture (proposed by Figueiredo, Meidanis, and Mello in mid-1990s) on edge-colouring chordal graphs of odd maximum degree ∆ holds when ∆ = 3. We discuss further decomposition algorithms for graph edge-colouring.\n
\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n Optimization System for Dynamic Flight Planning for Groups of Drones using Cooperation with Mobile Recharge Bases by Means of Multiagent System and Recursive Auctions.\n \n \n \n\n\n \n Robison C. Brito; José F. Loureiro; Eduardo Todt; and Andre L. P. Guedes.\n\n\n \n\n\n\n In
2019 IEEE 43rd Annual Computer Software and Applications Conference (COMPSAC), Milwaukee, Wisconsin, USA, 2019. IEEE\n
\n\n
\n\n
\n\n
\n\n \n\n \n \n doi\n \n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@InProceedings{Brito2019,\n title = {Optimization System for Dynamic Flight Planning for\n Groups of Drones using Cooperation with Mobile\n Recharge Bases by Means of Multiagent System and\n Recursive Auctions},\n author = {Robison C. Brito and José F. Loureiro and Eduardo\n Todt and Andre L. P. Guedes},\n booktitle = {2019 IEEE 43rd Annual Computer Software and\n Applications Conference (COMPSAC)},\n publisher = {IEEE},\n year = {2019},\n address = {Milwaukee, Wisconsin, USA},\n _keywords = {Universal2016},\n doi = {10.1109/COMPSAC.2019.10262}\n}\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n Anatome: Anatomy Teaching and Learning Designed for All.\n \n \n \n\n\n \n Márcia Valéria Rodrigues Ferreira; Laura Sánchez García; André Luiz Pires Guedes; Djanira Aparecida da Luz Veronez; Celia Regina Alves de Araújo Sandrini; and Carlos Eduardo de Araujo.\n\n\n \n\n\n\n In
Proc. SAC, pages 474-483, Limassol, Cyprus, 2019. \n
\n\n
\n\n
\n\n
\n\n \n\n \n \n doi\n \n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@InProceedings{Ferreira2019SAC,\n title = {Anatome: Anatomy Teaching and Learning Designed for\n All},\n author = {Ferreira, Márcia Valéria Rodrigues and García, Laura\n Sánchez and Guedes, André Luiz Pires and Veronez,\n Djanira Aparecida da Luz and Sandrini, Celia Regina\n Alves de Araújo and Araujo, Carlos Eduardo de},\n year = 2019,\n booktitle = {Proc. SAC},\n address = {Limassol, Cyprus},\n pages = {474-483},\n doi = {10.1145/3297280.3297324}\n}\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n On Subclasses of Circular Arc Bigraphs.\n \n \n \n \n\n\n \n M. Groshaus; A. L. P. Guedes; and F. S. Kolberg.\n\n\n \n\n\n\n In
III Workshop de Pesquisa em Computação dos Campos Gerais, volume 3, pages 68-73, Ponta Grossa, Paraná, 2019. \n
\n\n
\n\n
\n\n
\n\n \n \n
pdf\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n \n \n abstract \n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@InProceedings{GroshausGuedesKolbergWPCCG2019,\n author = {M. Groshaus and A. L. P. Guedes and F. S. Kolberg},\n title = {On Subclasses of Circular Arc Bigraphs},\n booktitle = {III Workshop de Pesquisa em Computação dos Campos\n Gerais},\n issn = {2526-1371},\n volume = {3},\n year = {2019},\n pages = {68-73},\n address = {Ponta Grossa, Paraná},\n abstract = {Circular arc (CA) bigraphs, a bipartite variation of\n circular arc graphs, are bipartite graphs such that,\n for each of its partite sets, there is a one-to-one\n correspondence between its elements and a family of\n arcs such that arcs from the opposing families\n intersect precisely if the corresponding vertices in\n the graph are neighbors. In this paper, we present\n results about different subclasses of circular arc\n bigraphs, including Helly and proper CA bigraphs, as\n well as circular convex bipartite (CCB) graphs.\n Keywords: Graph classes, Characterization, Helly,\n Circular arc bigraphs, Circular convex bipartite\n graphs.},\n _keywords = {Universal2016},\n url_pdf = {http://www.wpccg.pro.br/wpccg2019/papers/paper_21}\n}\n\n
\n
\n\n\n
\n Circular arc (CA) bigraphs, a bipartite variation of circular arc graphs, are bipartite graphs such that, for each of its partite sets, there is a one-to-one correspondence between its elements and a family of arcs such that arcs from the opposing families intersect precisely if the corresponding vertices in the graph are neighbors. In this paper, we present results about different subclasses of circular arc bigraphs, including Helly and proper CA bigraphs, as well as circular convex bipartite (CCB) graphs. Keywords: Graph classes, Characterization, Helly, Circular arc bigraphs, Circular convex bipartite graphs.\n
\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n Seleção Online de Features em Streaming Baseada em Alpha-Investing Para Dados de Ataques DDoS.\n \n \n \n \n\n\n \n Alissar Moussa; Michele Nogueira; and André Guedes.\n\n\n \n\n\n\n In
Anais do XXIV Workshop de Gerência e Operação de Redes e Serviços, pages 43-56, Porto Alegre, RS, Brasil, 2019. SBC\n
\n\n
\n\n
\n\n
\n\n \n \n
Paper\n \n \n\n \n \n doi\n \n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@InProceedings{MoussaNogueiraGuedes2019,\n author = {Alissar Moussa and Michele Nogueira and André Guedes},\n title = {Seleção Online de Features em Streaming Baseada em\n Alpha-Investing Para Dados de Ataques DDoS},\n booktitle = {Anais do XXIV Workshop de Gerência e Operação de\n Redes e Serviços},\n location = {Gramado},\n year = {2019},\n keywords = {},\n issn = {2595-2722},\n pages = {43-56},\n publisher = {SBC},\n address = {Porto Alegre, RS, Brasil},\n doi = {10.5753/wgrs.2019.7682},\n url =\n {https://sol.sbc.org.br/index.php/wgrs/article/view/7682}\n}\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n Algoritmos de planejamento de caminhos 3D.\n \n \n \n\n\n \n Cleiton Santos; and A. L. P. Guedes.\n\n\n \n\n\n\n In
Proc. Computer on the beach, Florianópolis, 2019. \n
\n\n
\n\n
\n\n
\n\n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@InProceedings{SantosGuedes2019,\n title = {Algoritmos de planejamento de caminhos {3D}},\n author = {Cleiton Santos and A. L. P. Guedes},\n year = 2019,\n booktitle = {Proc. Computer on the beach},\n address = {Florianópolis},\n _keywords = {Universal2016}\n}\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n Planejamento de caminhos 3D: Comparação dos algoritmos por grade 3D e grafo de visibilidade.\n \n \n \n \n\n\n \n C. A. Santos; and A. L. P. Guedes.\n\n\n \n\n\n\n In
III Workshop de Pesquisa em Computação dos Campos Gerais, volume 3, pages 116-121, Ponta Grossa, Paraná, 2019. \n
\n\n
\n\n
\n\n
\n\n \n \n
pdf\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n \n \n abstract \n \n\n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@InProceedings{SantosGuedesWPCCG2019,\n author = {C. A. Santos and A. L. P. Guedes},\n title = {Planejamento de caminhos 3D: Comparação dos\n algoritmos por grade 3D e grafo de visibilidade},\n booktitle = {III Workshop de Pesquisa em Computação dos Campos\n Gerais},\n issn = {2526-1371},\n volume = {3},\n year = {2019},\n pages = {116-121},\n address = {Ponta Grossa, Paraná},\n abstract = {Este artigo descreve o andamento de uma pesquisa\n focada em planejamento de caminhos 3D. O objetivo da\n pesquisa é encontrar algoritmos de baixa complexidade\n computacional, capazes de gerar um caminho próximo do\n ótimo em um ambiente controlado. Os algoritmos em\n estudo possuem como entrada a descrição do ambiente, e\n como saída o melhor caminho entre os pontos de origem\n e de destino. As abordagens por visibilidade e por\n grade são comparadas em ambientes simples. Também são\n propostas melhorias. Palavras-chave: Planejamento de\n caminhos 3D, Grafo de visibilidade 3D, Grade 3D.},\n _keywords = {Universal2016},\n url_pdf = {http://www.wpccg.pro.br/wpccg2019/papers/paper_25}\n}\n\n
\n
\n\n\n
\n Este artigo descreve o andamento de uma pesquisa focada em planejamento de caminhos 3D. O objetivo da pesquisa é encontrar algoritmos de baixa complexidade computacional, capazes de gerar um caminho próximo do ótimo em um ambiente controlado. Os algoritmos em estudo possuem como entrada a descrição do ambiente, e como saída o melhor caminho entre os pontos de origem e de destino. As abordagens por visibilidade e por grade são comparadas em ambientes simples. Também são propostas melhorias. Palavras-chave: Planejamento de caminhos 3D, Grafo de visibilidade 3D, Grade 3D.\n
\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n Novel Procedures for Graph Edge-colouring.\n \n \n \n \n\n\n \n Leandro Zatesko; Renato Carmo; and André Guedes.\n\n\n \n\n\n\n In
Anais do XXXII Concurso de Teses e Dissertações, Porto Alegre, RS, Brasil, 2019. SBC\n
\n\n
\n\n
\n\n
\n\n \n \n
Paper\n \n \n\n \n \n doi\n \n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 4 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@InProceedings{Zatesko2019CTDSBC,\n author = {Leandro Zatesko and Renato Carmo and André Guedes},\n title = {Novel Procedures for Graph Edge-colouring},\n booktitle = {Anais do XXXII Concurso de Teses e Dissertações},\n location = {Belém},\n year = {2019},\n _keywords = {Universal2016},\n issn = {0000-0000},\n publisher = {SBC},\n address = {Porto Alegre, RS, Brasil},\n _keywords = {Universal2016},\n doi = {10.5753/ctd.2019.6331},\n url =\n {https://sol.sbc.org.br/index.php/ctd/article/view/6331}\n}\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n Novel Procedures for Graph Edge-colouring.\n \n \n \n \n\n\n \n Leandro Zatesko; Renato Carmo; and André Guedes.\n\n\n \n\n\n\n In
Prêmio de Tese do LI Simpósio Brasileiro de Pesquisa Operacional, Campinas, GALOÁ, 2019. SBPO\n
Prêmio: melhor de tese de doutorado\n\n
\n\n
\n\n
\n\n \n \n
Paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 4 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@InProceedings{Zatesko2019CTDSBPO,\n author = {Leandro Zatesko and Renato Carmo and André Guedes},\n title = {Novel Procedures for Graph Edge-colouring},\n booktitle = {Prêmio de Tese do LI Simpósio Brasileiro de Pesquisa\n Operacional},\n location = {Limeira},\n year = {2019},\n _keywords = {Universal2016},\n issn = {0000-0000},\n publisher = {SBPO},\n address = {Campinas, GALOÁ},\n note = {Prêmio: melhor de tese de doutorado},\n _keywords = {Universal2016},\n url =\n {https://proceedings.science/sbpo-2019/papers/novel-procedures-for-graph-edge-colouring?lang=pt-br}\n}\n\n
\n
\n\n\n\n
\n\n\n\n\n\n