Biclique graph of bipartite permutation graphs. Groshaus, M., Guedes, A. L. P., & Puppo, J. P. Electronic Notes in Discrete Mathematics, 62:33–38, 2017. LAGOS'17 - IX Latin and American Algorithms, Graphs and Optimization.
Paper doi abstract bibtex Abstract The biclique graph KB(G) is the intersection graph of bicliques of a graph G. The aim of our work is to recognize graphs that are biclique graphs of bipartite permutation graphs. In this paper we prove that the biclique graph of a bipartite permutation graph is a K1,4-free interval graph, and we present a characterization of such graphs and a characterization of a subclass that leads to a polynomial time recognition algorithm.
@article{GroshausGuedesPuppo2017,
title = "Biclique graph of bipartite permutation graphs",
journal = "Electronic Notes in Discrete Mathematics",
volume = "62",
pages = "33--38",
year = "2017",
note = "LAGOS'17 - {IX} Latin and American Algorithms, Graphs and Optimization.",
issn = "1571-0653",
doi = "10.1016/j.endm.2017.10.007",
url = "https://www.sciencedirect.com/science/article/pii/S1571065317302457",
abstract_url = {https://lipn.univ-paris13.fr/Lagos2017/abstracts_final_short.pdf},
author = "M. Groshaus and A. L. P. Guedes and J. P. Puppo",
keywords = "Bicliques",
keywords = "Biclique graphs",
keywords = "Bipartite permutation graphs ",
abstract = "Abstract The biclique graph KB(G) is the intersection graph of bicliques of a graph G. The aim of our work is to recognize graphs that are biclique graphs of bipartite permutation graphs. In this paper we prove that the biclique graph of a bipartite permutation graph is a K1,4-free interval graph, and we present a characterization of such graphs and a characterization of a subclass that leads to a polynomial time recognition algorithm. "
}
Downloads: 0
{"_id":"uMae73dD3qrZqZ7Bi","bibbaseid":"groshaus-guedes-puppo-bicliquegraphofbipartitepermutationgraphs-2017","downloads":0,"creationDate":"2018-04-10T20:08:10.675Z","title":"Biclique graph of bipartite permutation graphs","author_short":["Groshaus, M.","Guedes, A. L. P.","Puppo, J. P."],"year":2017,"bibtype":"article","biburl":"http://www.inf.ufpr.br/teoria/universal2016/universal.bib","bibdata":{"bibtype":"article","type":"article","title":"Biclique graph of bipartite permutation graphs","journal":"Electronic Notes in Discrete Mathematics","volume":"62","pages":"33–38","year":"2017","note":"LAGOS'17 - IX Latin and American Algorithms, Graphs and Optimization.","issn":"1571-0653","doi":"10.1016/j.endm.2017.10.007","url":"https://www.sciencedirect.com/science/article/pii/S1571065317302457","abstract_url":"https://lipn.univ-paris13.fr/Lagos2017/abstracts_final_short.pdf","author":[{"firstnames":["M."],"propositions":[],"lastnames":["Groshaus"],"suffixes":[]},{"firstnames":["A.","L.","P."],"propositions":[],"lastnames":["Guedes"],"suffixes":[]},{"firstnames":["J.","P."],"propositions":[],"lastnames":["Puppo"],"suffixes":[]}],"keywords":"Bipartite permutation graphs ","abstract":"Abstract The biclique graph KB(G) is the intersection graph of bicliques of a graph G. The aim of our work is to recognize graphs that are biclique graphs of bipartite permutation graphs. In this paper we prove that the biclique graph of a bipartite permutation graph is a K1,4-free interval graph, and we present a characterization of such graphs and a characterization of a subclass that leads to a polynomial time recognition algorithm. ","bibtex":"@article{GroshausGuedesPuppo2017,\ntitle = \"Biclique graph of bipartite permutation graphs\",\njournal = \"Electronic Notes in Discrete Mathematics\",\nvolume = \"62\",\npages = \"33--38\",\nyear = \"2017\",\nnote = \"LAGOS'17 - {IX} Latin and American Algorithms, Graphs and Optimization.\",\nissn = \"1571-0653\",\ndoi = \"10.1016/j.endm.2017.10.007\",\nurl = \"https://www.sciencedirect.com/science/article/pii/S1571065317302457\",\nabstract_url = {https://lipn.univ-paris13.fr/Lagos2017/abstracts_final_short.pdf},\nauthor = \"M. Groshaus and A. L. P. Guedes and J. P. Puppo\",\nkeywords = \"Bicliques\",\nkeywords = \"Biclique graphs\",\nkeywords = \"Bipartite permutation graphs \",\nabstract = \"Abstract The biclique graph KB(G) is the intersection graph of bicliques of a graph G. The aim of our work is to recognize graphs that are biclique graphs of bipartite permutation graphs. In this paper we prove that the biclique graph of a bipartite permutation graph is a K1,4-free interval graph, and we present a characterization of such graphs and a characterization of a subclass that leads to a polynomial time recognition algorithm. \"\n}\n\n","author_short":["Groshaus, M.","Guedes, A. L. P.","Puppo, J. P."],"key":"GroshausGuedesPuppo2017","id":"GroshausGuedesPuppo2017","bibbaseid":"groshaus-guedes-puppo-bicliquegraphofbipartitepermutationgraphs-2017","role":"author","urls":{"Paper":"https://www.sciencedirect.com/science/article/pii/S1571065317302457"},"keyword":["Bipartite permutation graphs"],"metadata":{"authorlinks":{"guedes, a":"https://www.inf.ufpr.br/andre/producao.html"}},"downloads":0},"search_terms":["biclique","graph","bipartite","permutation","graphs","groshaus","guedes","puppo"],"keywords":["bipartite permutation graphs"],"authorIDs":["56d4f52e012e49233700010b","5aDCEbTc8DEcmwPjP","5de94e0cd574c6de01000015","5e06e3982eda19df01000053","5e180a689a3d0bde01000083","5e3b003855f0f2df0100010b","5e3b2a58255dcade01000067","5e3b3421255dcade01000116","5e446969084293df0100006c","5e4486d6ec14b3de01000083","5e46f963461d04f201000119","5e4e91ca9b7bbade01000156","5e4e951f9b7bbade010001d8","5e4ea40964b624de010000c8","5e4ed2722962cadf01000030","5e551b440096f9de0100007f","5e62a99208ebcade01000150","5e659ca25dd5c8de01000097","96kL4gCBP5FoqsRas","J2C57oh33kb32dCxz","bGjvG4AKHiX2cc7YG","fDLzHgeeX2HLGn9dM","m46QHpvf79WSptWRW","nhK8gHPJzMitxAzQ6","rZYT5zZRnwSxoFJa9","sJqxjCtsgbZxh8Zrk","xjLgNamFKzfeoqvdv"],"dataSources":["8EF7A9sBtzR7yAc4T","wKyTDzPCLmTgMwZxK","YZ4FB69ijWbW8PRYy"]}