Artículo
Eguía, M.; Soulignac, F.J. "Disimplicial arcs, transitive vertices, and disimplicial eliminations" (2015) Discrete Mathematics and Theoretical Computer Science. 17(2):101-118
Estamos trabajando para incorporar este artículo al repositorio
Consulte la política de Acceso Abierto del editor
Abstract:
In this article we deal with the problems of finding the disimplicial arcs of a digraph and recognizing some interesting graph classes defined by their existence. A diclique of a digraph is a pair V → W of sets of vertices such that v → w is an arc for every v ∈ V and w ∈ W. An arc v → w is disimplicial when it belongs to a unique maximal diclique. We show that the problem of finding the disimplicial arcs is equivalent, in terms of time and space complexity, to that of locating the transitive vertices. As a result, an efficient algorithm to find the bisimplicial edges of bipartite graphs is obtained. Then, we develop simple algorithms to build disimplicial elimination schemes, which can be used to generate bisimplicial elimination schemes for bipartite graphs. Finally, we study two classes related to perfect disimplicial elimination digraphs, namely weakly diclique irreducible digraphs and diclique irreducible digraphs. The former class is associated to finite posets, while the latter corresponds to dedekind complete finite posets. © 2015 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France.
Registro:
| Documento: | Artículo |
| Título: | Disimplicial arcs, transitive vertices, and disimplicial eliminations |
| Autor: | Eguía, M.; Soulignac, F.J. |
| Filiación: | Departamento de Computación, FCEN, Universidad de Buenos Aires, Argentina CONICET, Departamento de Ciencia y Tecnología, Universidad Nacional de Quilmes, Argentina |
| Palabras clave: | Bisimplicial edges of bipartite graphs; Bisimplicial elimination schemes; Dedekind digraphs; Diclique irreducible digraphs; Disimplicial arcs; Disimplicial elimination schemes; Transitive digraphs; Algorithms; Directed graphs; Set theory; Bipartite graphs; Dedekind digraphs; Diclique irreducible digraphs; Disimplicial arcs; Elimination scheme; Transitive digraphs; Graph theory |
| Año: | 2015 |
| Volumen: | 17 |
| Número: | 2 |
| Página de inicio: | 101 |
| Página de fin: | 118 |
| Título revista: | Discrete Mathematics and Theoretical Computer Science |
| Título revista abreviado: | Discrete Math. Theor. Comput. Sci. |
| ISSN: | 14627264 |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v17_n2_p101_Eguia |
Referencias:
- Bomhoff, M., Recognizing sparse perfect elimination bipartite graphs (2011) Computer Science-theory and Applications, Volume 6651 of Lecture Notes in Comput. Sci., pp. 443-455. , Springer, Heidelberg
- Bomhoff, M., Manthey, B., Bisimplicial edges in bipartite graphs (2013) Discrete Appl. Math., 161 (12), pp. 1699-1706
- Chiba, N., Nishizeki, T., Arboricity and subgraph listing algorithms (1985) SIAM J. Comput., 14 (1), pp. 210-223
- Dias, V.M.F., De Figueiredo, C.M.H., Szwarcfiter, J.L., On the generation of bicliques of a graph (2007) Discrete Appl. Math., 155 (14), pp. 1826-1832
- Goh, L., Rotem, D., Recognition of perfect elimination bipartite graphs (1982) Inform. Process. Lett., 15 (4), pp. 179-182
- Golumbic, M.C., Goss, C.F., Perfect elimination and chordal bipartite graphs (1978) J. Graph Theory, 2 (2), pp. 155-163
- Le Gall, F., Powers of tensors and fast matrix multiplication (2014) ISSAC 2014-Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, pp. 296-303. , ACM, New York
- Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L., Arboricity, h-index, and dynamic algorithms (2012) Theoret. Comput. Sci., 426-427, pp. 75-90
- Nash-Williams, C.S.J.A., Decomposition of finite graphs into forests (1964) J. London Math. Soc., 39, p. 12
- Rose, D.J., Tarjan, R.E., Algorithmic aspects of vertex elimination on directed graphs (1978) SIAM J. Appl. Math., 34 (1), pp. 176-197
- Spinrad, J.P., (2003) Efficient Graph Representations, Volume 19 of Fields Institute Monographs. American Mathematical Society, Providence, RI
- Spinrad, J.P., Recognizing quasi-triangulated graphs (2004) Discrete Appl. Math., 138 (1-2), pp. 203-213
- Wallis, W.D., Zhang, G.-H., On maximal clique irreducible graphs (1990) J. Combin. Math. Combin. Comput., 8, pp. 187-193
- Wang, T.-M., On characterizing weakly maximal clique irreducible graphs (2003) Proceedings of the Thirty-Fourth Southeastern International Conference on Combinatorics, Graph Theory and Computing, 163, pp. 177-188
Citas:
---------- APA ----------
Eguía, M. & Soulignac, F.J. (2015) . Disimplicial arcs, transitive vertices, and disimplicial eliminations. Discrete Mathematics and Theoretical Computer Science, 17(2), 101-118.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v17_n2_p101_Eguia [ ]
---------- CHICAGO ----------
Eguía, M., Soulignac, F.J. "Disimplicial arcs, transitive vertices, and disimplicial eliminations" . Discrete Mathematics and Theoretical Computer Science 17, no. 2 (2015) : 101-118.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v17_n2_p101_Eguia [ ]
---------- MLA ----------
Eguía, M., Soulignac, F.J. "Disimplicial arcs, transitive vertices, and disimplicial eliminations" . Discrete Mathematics and Theoretical Computer Science, vol. 17, no. 2, 2015, pp. 101-118.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v17_n2_p101_Eguia [ ]
---------- VANCOUVER ----------
Eguía, M., Soulignac, F.J. Disimplicial arcs, transitive vertices, and disimplicial eliminations. Discrete Math. Theor. Comput. Sci. 2015;17(2):101-118.Available from: https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v17_n2_p101_Eguia [ ]
