2026-07-22T06:27:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18584 2024-03-06T11:02:11Z ddc:004 open_access

An FPT Algorithm for Spanning Trees with Few Branch Vertices Parameterized by Modular-Width Gargano, Luisa Rescigno, Adele A. Spanning Trees Branch vertices Fixed-parameter tractable algorithms Modular-width 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Luisa Gargano and Adele A. Rescigno 2023 Is Part Of LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2023.50 urn:nbn:de:0030-drops-185843 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.50 eng https://creativecommons.org/licenses/by/4.0/legalcode