\n \n \n
\n
\n\n \n \n \n \n \n \n Biclique Graphs of K3-free Graphs and Bipartite Graphs.\n \n \n \n \n\n\n \n Marina Groshaus; and André L. P. Guedes.\n\n\n \n\n\n\n
Procedia Computer Science, 195: 230–238. 2021.\n
Proceedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium.\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\n\n\n
\n
@article{GroshausGuedesProcedia2021,\ntitle = "Biclique Graphs of K3-free Graphs and Bipartite\n Graphs",\n author = "Marina Groshaus and André L. P. Guedes",\n journal = {Procedia Computer Science},\n volume = {195},\n year = "2021",\n ISSN = {1877-0509},\n url = {http://dx.doi.org/10.1016/j.procs.2021.11.029},\n DOI = {10.1016/j.procs.2021.11.029},\n publisher = {Elsevier BV},\n pages = {230–238},\n note = {Proceedings of the XI Latin and American Algorithms,\n Graphs and Optimization Symposium.},\n keywords = {Bicliques, Biclique graphs, Intersection graphs,\n Triangle-free graphs, Bipartite graphs, Comparability\n graphs, Power of a graph},\n abstract = {A biclique of a graph is a maximal complete bipartite\n subgraph. The biclique graph of a graph G, KB(G),\n defined as the intersection graph of the bicliques of\n G, was introduced and characterized in 2010 by\n Groshaus and Szwarcfiter. However, this\n characterization does not lead to polynomial time\n recognition algorithms, and the time complexity of its\n recognition problem remains open. There are some works\n on this problem when restricted to some classes. In\n this work we give a characterization of the biclique\n graph of a K3-free graph G. We prove that KB(G) is the\n square graph of a particular graph which we call\n Mutually Included Biclique Graph of G,\n KBm(G). Although it does not lead to a polynomial time\n recognition algorithm, it gives a new tool to prove\n properties of biclique graphs (restricted to K3-free\n graphs) using known properties of square graphs. For\n instance we generalize a property about induced P3's\n in biclique graphs to a property about stars and\n proved a conjecture posted by Groshaus and Montero,\n when restricted to K3-free graphs. Also we give\n another characterization of the class of biclique\n graphs of bipartite graphs. We prove that\n KB(bipartite) = (IIC-comparability)2, where\n IIC-comparability is a subclass of comparability\n graphs that we call Interval Intersection Closed\n Comparability.}\n}\n\n
\n
\n\n\n
\n A biclique of a graph is a maximal complete bipartite subgraph. The biclique graph of a graph G, KB(G), defined as the intersection graph of the bicliques of G, was introduced and characterized in 2010 by Groshaus and Szwarcfiter. However, this characterization does not lead to polynomial time recognition algorithms, and the time complexity of its recognition problem remains open. There are some works on this problem when restricted to some classes. In this work we give a characterization of the biclique graph of a K3-free graph G. We prove that KB(G) is the square graph of a particular graph which we call Mutually Included Biclique Graph of G, KBm(G). Although it does not lead to a polynomial time recognition algorithm, it gives a new tool to prove properties of biclique graphs (restricted to K3-free graphs) using known properties of square graphs. For instance we generalize a property about induced P3's in biclique graphs to a property about stars and proved a conjecture posted by Groshaus and Montero, when restricted to K3-free graphs. Also we give another characterization of the class of biclique graphs of bipartite graphs. We prove that KB(bipartite) = (IIC-comparability)2, where IIC-comparability is a subclass of comparability graphs that we call Interval Intersection Closed Comparability.\n
\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n On feedback vertex set in reducible flow hypergraphs.\n \n \n \n \n\n\n \n Luerbio Faria; André L. P. Guedes; and Lilian Markenzon.\n\n\n \n\n\n\n
Procedia Computer Science, 195: 212-220. 2021.\n
Proceedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium.\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 2 downloads\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{FariaGuedesMarkenzonProcedia2021,\ntitle = "On feedback vertex set in reducible flow hypergraphs",\njournal = {Procedia Computer Science},\nvolume = {195},\npages = {212-220},\nyear = {2021},\nnote = {Proceedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium.},\nissn = {1877-0509},\ndoi = {https://doi.org/10.1016/j.procs.2021.11.027},\nurl = {https://www.sciencedirect.com/science/article/pii/S1877050921021669},\nauthor = {Luerbio Faria and André L. P. Guedes and Lilian Markenzon},\nkeywords = {directed hypergraphs, feedback vertex set, NP-complete, approximation algorithms},\nabstract = {A directed hypergraph H = (V, A) is a finite set of vertices V and a set of hyper-arcs A, where each hyper-arc is an ordered pair of nonempty subsets of vertices. A flow hypergraph H = (V, A, s) is a triple, such that (V, A) is a directed hypergraph, s e V is a distinguished vertex such that s reaches every vertex of V. Reducible flow hypergraphs are a generalization of Hecht and Ullman’s reducible flowgraphs. The feedback vertex set (fvs) decision problem has a directed hypergraph H and an integer k ≥ 0 as input and the question is whether there is V'⊆V, |V' |≤k such that H\\V' is an acyclic directed hypergraph. It is known that fvs is polynomial time solvable for reducible flowgraphs. In this article we prove that fvs is NP-complete for reducible flow hypergraphs showing a reduction from 3-satisfiability problem with at most 3 occurrences per variable (3sat3-). We exhibit a polynomial-time ∆-approximation for fvs in reducible flow hypergraphs, where ∆ is the maximum number of hyper-arcs adjacent to a vertex of H.}\n}\n\n
\n
\n\n\n
\n A directed hypergraph H = (V, A) is a finite set of vertices V and a set of hyper-arcs A, where each hyper-arc is an ordered pair of nonempty subsets of vertices. A flow hypergraph H = (V, A, s) is a triple, such that (V, A) is a directed hypergraph, s e V is a distinguished vertex such that s reaches every vertex of V. Reducible flow hypergraphs are a generalization of Hecht and Ullman’s reducible flowgraphs. The feedback vertex set (fvs) decision problem has a directed hypergraph H and an integer k ≥ 0 as input and the question is whether there is V'⊆V, |V' |≤k such that H\\V' is an acyclic directed hypergraph. It is known that fvs is polynomial time solvable for reducible flowgraphs. In this article we prove that fvs is NP-complete for reducible flow hypergraphs showing a reduction from 3-satisfiability problem with at most 3 occurrences per variable (3sat3-). We exhibit a polynomial-time ∆-approximation for fvs in reducible flow hypergraphs, where ∆ is the maximum number of hyper-arcs adjacent to a vertex of H.\n
\n\n\n
\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n FPT and kernelization algorithms for the induced tree problem.\n \n \n \n\n\n \n Guilherme Castro Mendes Gomes; Vinicius F Santos; Murilo VG Silva; and Jayme L Szwarcfiter.\n\n\n \n\n\n\n In
International Conference on Algorithms and Complexity, pages 158–172, 2021. Springer\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{gomes2021fpt,\n title={FPT and kernelization algorithms for the induced tree problem},\n author={Gomes, Guilherme Castro Mendes and dos Santos, Vinicius F and da Silva, Murilo VG and Szwarcfiter, Jayme L},\n booktitle={International Conference on Algorithms and Complexity},\n pages={158--172},\n year={2021},\n organization={Springer}\n}\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n Sobre Rotulações $\\mathcal{L}(h, k)$ de Caterpillars.\n \n \n \n \n\n\n \n J. P. K. Castilho; C. N. Campos; and L. M. Zatesko.\n\n\n \n\n\n\n In
Proc. 41st Congress of the Brazilian Computer Society (CSBC '21/VI ETC), pages 62–65, Florianópolis, Brazil, 2021. \n
\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 \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@inproceedings{castilho21etc,\n author = {J. P. K. Castilho and C. N. Campos and L. M. Zatesko},\n language = {portuguese},\n year = 2021,\n title = {Sobre Rotulações $\\mathcal{L}(h, k)$ de Caterpillars},\n booktitle = {Proc. 41st Congress of the Brazilian Computer Society\n(CSBC '21/VI ETC)},\n address = {Florian\\'opolis, Brazil},\n issn = {2595-6116},\n url = {https://doi.org/10.5753/etc.2021.16381},\n pages = {62--65}\n}\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n An Extended Adjacency Lemma for Graph Edge-Coloring.\n \n \n \n \n\n\n \n T. H. F. M. Cunha; and L. M. Zatesko.\n\n\n \n\n\n\n In
Proc. 4th Workshop de Pesquisa em Computação dos Campos Gerais (WPCCG '21), pages 43–47, Ponta Grossa, Brazil, 2021. \n
\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 \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@inproceedings{thiago21wpccg,\n author = {T. H. F. M. Cunha and L. M. Zatesko},\n language = {english},\n year = 2021,\n title = {An Extended Adjacency Lemma for Graph Edge-Coloring},\n booktitle = {Proc. 4th Workshop de Pesquisa em Computação dos\nCampos Gerais (WPCCG '21)},\n address = {Ponta Grossa, Brazil},\n issn = {2526-1371},\n pages = {43--47},\n url = {http://www.wpccg.pro.br/volume004.html}\n}\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n Proper $\\mathcal{L}(h, k)$-labelling of Caterpillars and Multisunlets.\n \n \n \n \n\n\n \n J. P. K. Castilho; C. N. Campos; and L. M. Zatesko.\n\n\n \n\n\n\n In
Proc. 4th Workshop de Pesquisa em Computação dos Campos Gerais (WPCCG '21), pages 48–53, Ponta Grossa, Brazil, 2021. \n
\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 \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@inproceedings{castilho21wpccg,\n author = {J. P. K. Castilho and C. N. Campos and L. M. Zatesko},\n language = {english},\n year = 2021,\n title = {Proper $\\mathcal{L}(h, k)$-labelling of Caterpillars and\nMultisunlets},\n booktitle = {Proc. 4th Workshop de Pesquisa em Computação dos\nCampos Gerais (WPCCG '21)},\n address = {Ponta Grossa, Brazil},\n issn = {2526-1371},\n pages = {48--53},\n url = {http://www.wpccg.pro.br/volume004.html}\n}\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n Grover's Quantum Algorithm and the Maximum Clique Problem.\n \n \n \n \n\n\n \n M. G. Dias; and L. M. Zatesko.\n\n\n \n\n\n\n In
Proc. 4th Workshop de Pesquisa em Computação dos Campos Gerais (WPCCG '21), pages 54–59, Ponta Grossa, Brazil, 2021. \n
\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 \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@inproceedings{matheus21wpccg,\n author = {M. G. Dias and L. M. Zatesko},\n language = {english},\n year = 2021,\n title = {Grover's Quantum Algorithm and the Maximum Clique\nProblem},\n booktitle = {Proc. 4th Workshop de Pesquisa em Computação dos\nCampos Gerais (WPCCG '21)},\n address = {Ponta Grossa, Brazil},\n issn = {2526-1371},\n pages = {54--59},\n url = {http://www.wpccg.pro.br/volume004.html}\n}\n\n
\n
\n\n\n\n
\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n Problema APSP via Dimensão-VC e Médias de Rademacher.\n \n \n \n \n\n\n \n Murilo V. G. da Silva Lima; and Andre L. Vignatti.\n\n\n \n\n\n\n In
Proc. 41st Congress of the Brazilian Computer Society (CSBC '21/VI ETC), pages 13–16, Florianópolis, Brazil, 2021. \n
\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 \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@inproceedings{Lima21etc,\n author = {Alane M. de Lima, Murilo V. G. da Silva and Andre L. Vignatti},\n language = {portuguese},\n year = 2021,\n title = {Problema APSP via Dimensão-VC e Médias de Rademacher},\n booktitle = {Proc. 41st Congress of the Brazilian Computer Society\n(CSBC '21/VI ETC)},\n address = {Florian\\'opolis, Brazil},\n issn = {2595-6116},\n url = {https://doi.org/10.5753/etc.2021.16381},\n pages = {13--16}\n}\n\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n The generalized influence blocking maximization problem.\n \n \n \n\n\n \n Andre L. Vignatti Fernando Erd; and Murilo V.G. Silva.\n\n\n \n\n\n\n
Soc. Netw. Anal. Min., 11: 55. 2021.\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
@article{erd21,\n title={The generalized influence blocking maximization problem},\n author={Fernando Erd, Andre L. Vignatti and Murilo V.G. da Silva},\n journal={Soc. Netw. Anal. Min.},\n volume={11},\n pages={55},\n year={2021},\n publisher={Springer Nature}\n}\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n Sample complexity in graph problems (contributed talk).\n \n \n \n\n\n \n Murilo V. G. da Silva Lima; and Andre L. Vignatti.\n\n\n \n\n\n\n In 2021. \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{canadam21,\n author = {Alane M. de Lima, Murilo V. G. da Silva and Andre L. Vignatti},\n title = {Sample complexity in graph problems (contributed talk)},\n language = {english},\n year = 2021\n}\n\n\n\n\n
\n
\n\n\n\n
\n\n\n\n\n\n