Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2020.13
URN: urn:nbn:de:0030-drops-128790
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12879/
Beisegel, Jesse ; Köhler, Ekkehard ; Scheffler, Robert ; Strehler, Martin
Linear Time LexDFS on Chordal Graphs
| pdf-format: |
|
Abstract
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).
BibTeX - Entry
@InProceedings{beisegel_et_al:LIPIcs:2020:12879,
author = {Jesse Beisegel and Ekkehard K{\"o}hler and Robert Scheffler and Martin Strehler},
title = {{Linear Time LexDFS on Chordal Graphs}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {13:1--13:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-162-7},
ISSN = {1868-8969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12879},
URN = {urn:nbn:de:0030-drops-128790},
doi = {10.4230/LIPIcs.ESA.2020.13},
annote = {Keywords: LexDFS, chordal graphs, linear time implementation, search trees, LexBFS}
}
| Keywords: | LexDFS, chordal graphs, linear time implementation, search trees, LexBFS | |
| Seminar: | 28th Annual European Symposium on Algorithms (ESA 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 26.08.2020 |
