Geodesic
Disimplicial arcs, transitive vertices, and disimplicial eliminations
Discrete mathematics & theoretical computer science, Tome 17 (2015-2016) no. 2.

Voir la notice de l'article provenant de la source Episciences

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 <i>diclique</i> of a digraph is a pair $V$ &rarr; $W$ of sets of vertices such that $v$ &rarr; $w$ is an arc for every $v$ &isin; $V$ and $w$ &isin; $W$. An arc $v$ &rarr; $w$ is <i>disimplicial</i> 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. 
@article{DMTCS_2015_17_2_a3,
     author = {Eguia, Martiniano and Soulignac, Francisco},
     title = {Disimplicial arcs, transitive vertices, and disimplicial eliminations},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {17},
     number = {2},
     year = {2015-2016},
     doi = {10.46298/dmtcs.2131},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2131/}
}
TY  - JOUR
AU  - Eguia, Martiniano
AU  - Soulignac, Francisco
TI  - Disimplicial arcs, transitive vertices, and disimplicial eliminations
JO  - Discrete mathematics & theoretical computer science
PY  - 2015-2016
VL  - 17
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2131/
DO  - 10.46298/dmtcs.2131
LA  - en
ID  - DMTCS_2015_17_2_a3
ER  - 
%0 Journal Article
%A Eguia, Martiniano
%A Soulignac, Francisco
%T Disimplicial arcs, transitive vertices, and disimplicial eliminations
%J Discrete mathematics & theoretical computer science
%D 2015-2016
%V 17
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2131/
%R 10.46298/dmtcs.2131
%G en
%F DMTCS_2015_17_2_a3
Eguia, Martiniano; Soulignac, Francisco. Disimplicial arcs, transitive vertices, and disimplicial eliminations. Discrete mathematics & theoretical computer science, Tome 17 (2015-2016) no. 2. doi : 10.46298/dmtcs.2131. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2131/

Cité par Sources :