License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2023.50
URN: urn:nbn:de:0030-drops-185843
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18584/
Go to the corresponding LIPIcs Volume Portal

Gargano, Luisa ; Rescigno, Adele A.

An FPT Algorithm for Spanning Trees with Few Branch Vertices Parameterized by Modular-Width

pdf-format:
LIPIcs-MFCS-2023-50.pdf (0.8 MB)

Abstract

The minimum branch vertices spanning tree problem consists in finding a spanning tree T of an input graph G having the minimum number of branch vertices, that is, vertices of degree at least three in T. This NP-hard problem has been widely studied in the literature and has many important applications in network design and optimization. Algorithmic and combinatorial aspects of the problem have been extensively studied and its fixed parameter tractability has been recently considered. In this paper we focus on modular-width and show that the problem of finding a spanning tree with the minimum number of branch vertices is FPT with respect to this parameter.

BibTeX - Entry

@InProceedings{gargano_et_al:LIPIcs.MFCS.2023.50,
  author =	{Gargano, Luisa and Rescigno, Adele A.},
  title =	{{An FPT Algorithm for Spanning Trees with Few Branch Vertices Parameterized by Modular-Width}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{50:1--50:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18584},
  URN =		{urn:nbn:de:0030-drops-185843},
  doi =		{10.4230/LIPIcs.MFCS.2023.50},
  annote =	{Keywords: Spanning Trees, Branch vertices, Fixed-parameter tractable algorithms, Modular-width}
}

Keywords: Spanning Trees, Branch vertices, Fixed-parameter tractable algorithms, Modular-width
Collection: 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Issue Date: 2023
Date of publication: 21.08.2023

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