Geodesic
On the End-Vertex Problem of Graph Searches
Discrete mathematics & theoretical computer science, ICGT 2018, Tome 21 (2019) no. 1

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

End vertices of graph searches can exhibit strong structural properties and are crucial for many graph algorithms. The problem of deciding whether a given vertex of a graph is an end-vertex of a particular search was first introduced by Corneil, K\"ohler and Lanlignel in 2010. There they showed that this problem is in fact NP-complete for LBFS on weakly chordal graphs. A similar result for BFS was obtained by Charbit, Habib and Mamcarz in 2014. Here, we prove that the end-vertex problem is NP-complete for MNS on weakly chordal graphs and for MCS on general graphs. Moreover, building on previous results, we show that this problem is linear for various searches on split and unit interval graphs. 
@article{DMTCS_2019_21_1_a12,
     author = {Beisegel, Jesse and Denkert, Carolin and K\"ohler, Ekkehard and Krnc, Matja\v{z} and Piva\v{c}, Nevena and Scheffler, Robert and Strehler, Martin},
     title = {On the {End-Vertex} {Problem} of {Graph} {Searches}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {21},
     number = {1},
     year = {2019},
     doi = {10.23638/DMTCS-21-1-13},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-13/}
}
TY  - JOUR
AU  - Beisegel, Jesse
AU  - Denkert, Carolin
AU  - Köhler, Ekkehard
AU  - Krnc, Matjaž
AU  - Pivač, Nevena
AU  - Scheffler, Robert
AU  - Strehler, Martin
TI  - On the End-Vertex Problem of Graph Searches
JO  - Discrete mathematics & theoretical computer science
PY  - 2019
VL  - 21
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-13/
DO  - 10.23638/DMTCS-21-1-13
LA  - en
ID  - DMTCS_2019_21_1_a12
ER  - 
%0 Journal Article
%A Beisegel, Jesse
%A Denkert, Carolin
%A Köhler, Ekkehard
%A Krnc, Matjaž
%A Pivač, Nevena
%A Scheffler, Robert
%A Strehler, Martin
%T On the End-Vertex Problem of Graph Searches
%J Discrete mathematics & theoretical computer science
%D 2019
%V 21
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-13/
%R 10.23638/DMTCS-21-1-13
%G en
%F DMTCS_2019_21_1_a12
Beisegel, Jesse; Denkert, Carolin; Köhler, Ekkehard; Krnc, Matjaž; Pivač, Nevena; Scheffler, Robert; Strehler, Martin. On the End-Vertex Problem of Graph Searches. Discrete mathematics & theoretical computer science, ICGT 2018, Tome 21 (2019) no. 1. doi: 10.23638/DMTCS-21-1-13

Cité par Sources :