Search Results

Documents authored by Beisegel, Jesse

Document
DOI: 10.4230/LIPIcs.SWAT.2024.7
The Simultaneous Interval Number: A New Width Parameter that Measures the Similarity to Interval Graphs

Authors: Jesse Beisegel, Nina Chiarelli, Ekkehard Köhler, Martin Milanič, Peter Muršič, and Robert Scheffler

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
We propose a novel way of generalizing the class of interval graphs, via a graph width parameter called simultaneous interval number. This parameter is related to the simultaneous representation problem for interval graphs and defined as the smallest number d of labels such that the graph admits a d-simultaneous interval representation, that is, an assignment of intervals and label sets to the vertices such that two vertices are adjacent if and only if the corresponding intervals, as well as their label sets, intersect. We show that this parameter is NP-hard to compute and give several bounds for the parameter, showing in particular that it is sandwiched between pathwidth and linear mim-width. For classes of graphs with bounded parameter values, assuming that the graph is equipped with a simultaneous interval representation with a constant number of labels, we give FPT algorithms for the clique, independent set, and dominating set problems, and hardness results for the independent dominating set and coloring problems. The FPT results for independent set and dominating set are for the simultaneous interval number plus solution size. In contrast, both problems are known to be 𝖶[1]-hard for linear mim-width plus solution size.
Cite as

Jesse Beisegel, Nina Chiarelli, Ekkehard Köhler, Martin Milanič, Peter Muršič, and Robert Scheffler. The Simultaneous Interval Number: A New Width Parameter that Measures the Similarity to Interval Graphs. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{beisegel_et_al:LIPIcs.SWAT.2024.7,
  author =	{Beisegel, Jesse and Chiarelli, Nina and K\"{o}hler, Ekkehard and Milani\v{c}, Martin and Mur\v{s}i\v{c}, Peter and Scheffler, Robert},
  title =	{{The Simultaneous Interval Number: A New Width Parameter that Measures the Similarity to Interval Graphs}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{7:1--7:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.7},
  URN =		{urn:nbn:de:0030-drops-200470},
  doi =		{10.4230/LIPIcs.SWAT.2024.7},
  annote =	{Keywords: Interval graph, simultaneous representation, width parameter, algorithm, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.13
Linear Time LexDFS on Chordal Graphs

Authors: Jesse Beisegel, Ekkehard Köhler, Robert Scheffler, and Martin Strehler

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

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).
Cite as

Jesse Beisegel, Ekkehard Köhler, Robert Scheffler, and Martin Strehler. Linear Time LexDFS on Chordal Graphs. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{beisegel_et_al:LIPIcs.ESA.2020.13,
  author =	{Beisegel, Jesse and K\"{o}hler, Ekkehard and Scheffler, Robert and Strehler, Martin},
  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 =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.13},
  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}
}
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact