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.
Notas
Trabajo publicado en Lecture Notes in Computer Science book series (LNCS, vol. 6410)
Información general
Fecha de exposición:2010
Fecha de publicación:2010
Idioma del documento:Español
Evento:36th International Workshop (WG 2010) (Zarós, Crete, Greece, June 28-30, 2010)
Institución de origen:Facultad de Ciencias Exactas
Excepto donde se diga explícitamente, este item se publica bajo la siguiente licencia Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)