Disimplicial arcs, transitive vertices, and disimplicial eliminations - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2015

Disimplicial arcs, transitive vertices, and disimplicial eliminations

Résumé

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.
Fichier principal
Vignette du fichier
2687-9774-1-PB.pdf (341.56 Ko) Télécharger le fichier
Origine : Accord explicite pour ce dépôt
Loading...

Dates et versions

hal-01349046 , version 1 (26-07-2016)

Identifiants

Citer

Martiniano Eguia, Francisco J. Soulignac. Disimplicial arcs, transitive vertices, and disimplicial eliminations. Discrete Mathematics and Theoretical Computer Science, 2015, Vol. 17 no.2 (2), pp.101-118. ⟨10.46298/dmtcs.2131⟩. ⟨hal-01349046⟩

Collections

TDS-MACS
35 Consultations
892 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More