From path graphs to directed path graphs

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 bet...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Chaplick, Steven, Gutiérrez, Marisa, Lévêque, Benjamin, Tondato, Silvia Beatriz
Formato: Objeto de conferencia
Lenguaje:Español
Publicado: 2010
Materias:
Matemática
Combinatorics
Discrete mathematics
Longest path problem
Mathematics
Pathwidth
Induced path
Cograph
Indifference graph
Widest path problem
Hamiltonian path
Path (graph theory)
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/127414
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-127414
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Español
topic Matemática
Combinatorics
Discrete mathematics
Longest path problem
Mathematics
Pathwidth
Induced path
Cograph
Indifference graph
Widest path problem
Hamiltonian path
Path (graph theory)
spellingShingle Matemática
Combinatorics
Discrete mathematics
Longest path problem
Mathematics
Pathwidth
Induced path
Cograph
Indifference graph
Widest path problem
Hamiltonian path
Path (graph theory)
Chaplick, Steven
Gutiérrez, Marisa
Lévêque, Benjamin
Tondato, Silvia Beatriz
From path graphs to directed path graphs
topic_facet Matemática
Combinatorics
Discrete mathematics
Longest path problem
Mathematics
Pathwidth
Induced path
Cograph
Indifference graph
Widest path problem
Hamiltonian path
Path (graph theory)
description 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.
format Objeto de conferencia
Objeto de conferencia
author Chaplick, Steven
Gutiérrez, Marisa
Lévêque, Benjamin
Tondato, Silvia Beatriz
author_facet Chaplick, Steven
Gutiérrez, Marisa
Lévêque, Benjamin
Tondato, Silvia Beatriz
author_sort Chaplick, Steven
title From path graphs to directed path graphs
title_short From path graphs to directed path graphs
title_full From path graphs to directed path graphs
title_fullStr From path graphs to directed path graphs
title_full_unstemmed From path graphs to directed path graphs
title_sort from path graphs to directed path graphs
publishDate 2010
url http://sedici.unlp.edu.ar/handle/10915/127414
work_keys_str_mv AT chaplicksteven frompathgraphstodirectedpathgraphs
AT gutierrezmarisa frompathgraphstodirectedpathgraphs
AT levequebenjamin frompathgraphstodirectedpathgraphs
AT tondatosilviabeatriz frompathgraphstodirectedpathgraphs
bdutipo_str Repositorios
_version_ 1764820451677175809

Ejemplares similares