2026-07-23T03:27:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12879 2024-03-06T10:50:58Z ddc:004 open_access

Linear Time LexDFS on Chordal Graphs Beisegel, Jesse Köhler, Ekkehard Scheffler, Robert Strehler, Martin LexDFS chordal graphs linear time implementation search trees LexBFS Lexicographic Depth First Search (LexDFS) is a special variant of a Depth First Search (DFS), which was introduced by Corneil and Krueger in 2008. While this search has been used in various applications, in contrast to other graph searches, no general linear time implementation is known to date. In 2014, Köhler and Mouatadid achieved linear running time to compute some special LexDFS orderings for cocomparability graphs. In this paper, we present a linear time implementation of LexDFS for chordal graphs. Our algorithm even implements the extended version LexDFS^+ and is, therefore, able to find any LexDFS ordering for this graph class. To the best of our knowledge this is the first unrestricted linear time implementation of LexDFS on a non-trivial graph class. In the algorithm we use a search tree computed by Lexicographic Breadth First Search (LexBFS). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jesse Beisegel and Ekkehard Köhler and Robert Scheffler and Martin Strehler 2020 Is Part Of LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2020.13 urn:nbn:de:0030-drops-128790 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.13 eng https://creativecommons.org/licenses/by/3.0/legalcode