Disimplicial arcs, transitive vertices, and disimplicial eliminations
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 disimpli...
| Autores principales: | , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_14627264_v17_n2_p101_Eguia |
| Aporte de: |
| id |
todo:paper_14627264_v17_n2_p101_Eguia |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_14627264_v17_n2_p101_Eguia2023-10-03T16:16:39Z Disimplicial arcs, transitive vertices, and disimplicial eliminations Eguía, M. Soulignac, F.J. 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 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. Fil:Soulignac, F.J. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_14627264_v17_n2_p101_Eguia |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-134 |
| collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
| topic |
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 |
| spellingShingle |
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 Eguía, M. Soulignac, F.J. Disimplicial arcs, transitive vertices, and disimplicial eliminations |
| topic_facet |
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 |
| description |
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. |
| format |
JOUR |
| author |
Eguía, M. Soulignac, F.J. |
| author_facet |
Eguía, M. Soulignac, F.J. |
| author_sort |
Eguía, M. |
| title |
Disimplicial arcs, transitive vertices, and disimplicial eliminations |
| title_short |
Disimplicial arcs, transitive vertices, and disimplicial eliminations |
| title_full |
Disimplicial arcs, transitive vertices, and disimplicial eliminations |
| title_fullStr |
Disimplicial arcs, transitive vertices, and disimplicial eliminations |
| title_full_unstemmed |
Disimplicial arcs, transitive vertices, and disimplicial eliminations |
| title_sort |
disimplicial arcs, transitive vertices, and disimplicial eliminations |
| url |
http://hdl.handle.net/20.500.12110/paper_14627264_v17_n2_p101_Eguia |
| work_keys_str_mv |
AT eguiam disimplicialarcstransitiveverticesanddisimplicialeliminations AT soulignacfj disimplicialarcstransitiveverticesanddisimplicialeliminations |
| _version_ |
1807324493804208128 |