Jesse Beisegel ; Carolin Denkert ; Ekkehard Köhler ; Matjaž Krnc ; Nevena Pivač et al. - On the End-Vertex Problem of Graph Searches

dmtcs:4937 - Discrete Mathematics & Theoretical Computer Science, June 13, 2019, vol. 21 no. 1, ICGT 2018 - https://doi.org/10.23638/DMTCS-21-1-13
On the End-Vertex Problem of Graph SearchesArticle

Authors: Jesse Beisegel ; Carolin Denkert ; Ekkehard Köhler ; Matjaž Krnc ; Nevena Pivač ; Robert Scheffler ; Martin Strehler

    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öhler 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.


    Volume: vol. 21 no. 1, ICGT 2018
    Published on: June 13, 2019
    Accepted on: May 28, 2019
    Submitted on: October 31, 2018
    Keywords: Computer Science - Discrete Mathematics
    Funding:
      Source : OpenAIRE Graph
    • Renewable materials and healthy environments research and innovation centre of excellence; Funder: European Commission; Code: 739574

    3 Documents citing this article

    Consultation statistics

    This page has been seen 846 times.
    This article's PDF has been downloaded 389 times.