License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12879/
Go to the corresponding LIPIcs Volume Portal

Beisegel, Jesse ; Köhler, Ekkehard ; Scheffler, Robert ; Strehler, Martin

Linear Time LexDFS on Chordal Graphs

pdf-format:
LIPIcs-ESA-2020-13.pdf (0.5 MB)

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
Collection: 28th Annual European Symposium on Algorithms (ESA 2020)
Issue Date: 2020
Date of publication: 26.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI