From Path Graphs to Directed Path Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2010

From Path Graphs to Directed Path Graphs

Résumé

We present a linear time algorithm to greedily orient the edges of a path graph model to obtain a directed path graph model (when possible). Moreover we extend this algorithm to find an odd sun when the method fails. This algorithm has several interesting consequences concerning the relationship between path graphs and directed path graphs. One is that for a directed path graph, path graph models and directed path graph models are the same. Another consequence concerns the difference between path graphs and directed path graphs in terms of forbidden induced subgraphs. This can be used to deduce the forbidden induced subgraph characterization of directed path graphs from the forbidden induced subgraph characterization of path graphs. The last consequence is algorithmic and shows that the recognition of directed path graphs is not more difficult than the recognition of path graphs.
Fichier principal
Vignette du fichier
From_Path_Graphs_to_Directed_Path_Graphs.pdf (298.88 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

lirmm-00620726 , version 1 (16-09-2019)

Identifiants

Citer

Steve Chaplick, Marisa Gutierrez, Benjamin Lévêque, Silvia Tondato. From Path Graphs to Directed Path Graphs. WG 2010 - 36th International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2010, Zarós, Greece. pp.256-265, ⟨10.1007/978-3-642-16926-7_24⟩. ⟨lirmm-00620726⟩
117 Consultations
277 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More