TUHH Open Research
Help
  • Log In
    New user? Click here to register.Have you forgotten your password?
  • English
  • Deutsch
  • Communities & Collections
  • Publications
  • Research Data
  • People
  • Institutions
  • Projects
  • Statistics
  1. Home
  2. TUHH
  3. Publications
  4. Domination and cut problems on chordal graphs with bounded leafage
 
Options

Domination and cut problems on chordal graphs with bounded leafage

Citation Link: https://doi.org/10.15480/882.9101
Publikationstyp
Journal Article
Date Issued
2024-05
Sprache
English
Author(s)
Galby, Esther  
Flugzeug-Kabinensysteme M-25  
Marx, Dániel  
Schepper, Philipp  
Sharma, Roohani  
Tale, Prafullkumar  
TORE-DOI
10.15480/882.9101
TORE-URI
https://hdl.handle.net/11420/45292
Journal
Algorithmica  
Volume
86
Issue
5
Start Page
1428
End Page
1474
Citation
Algorithmica 86 (5): 1428-1474 (2023)
Publisher DOI
10.1007/s00453-023-01196-y
Scopus ID
2-s2.0-85180867145
Publisher
Springer
The leafage of a chordal graph G is the minimum integer ℓ such that G can be realized as an intersection graph of subtrees of a tree with ℓ leaves. We consider structural parameterization by the leafage of classical domination and cut problems on chordal graphs. Fomin, Golovach, and Raymond [ESA 2018, Algorithmica 2020] proved, among other things, that Dominating Set on chordal graphs admits an algorithm running in time 2O(ℓ2)·nO(1) . We present a conceptually much simpler algorithm that runs in time 2 O(ℓ)· nO(1) . We extend our approach to obtain similar results for Connected Dominating Set and Steiner Tree. We then consider the two classical cut problems MultiCut with Undeletable Terminals and Multiway Cut with Undeletable Terminals. We prove that the former is W[1]-hard when parameterized by the leafage and complement this result by presenting a simple nO(ℓ) -time algorithm. To our surprise, we find that Multiway Cut with Undeletable Terminals on chordal graphs can be solved, in contrast, in nO(1) -time.
Subjects
Chordal graphs
Dominating set
FPT algorithms
Leafage
MultiCut with undeletable terminals
Multiway cut with undeletable terminals
DDC Class
004: Computer Sciences
Funding(s)
Projekt DEAL  
Publication version
publishedVersion
Lizenz
https://creativecommons.org/licenses/by/4.0/
Loading...
Thumbnail Image
Name

s00453-023-01196-y.pdf

Type

Main Article

Size

782.85 KB

Format

Adobe PDF

TUHH
Weiterführende Links
  • Contact
  • Send Feedback
  • Cookie settings
  • Privacy policy
  • Impress
DSpace Software

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science
Design by effective webwork GmbH

  • Deutsche NationalbibliothekDeutsche Nationalbibliothek
  • ORCiD Member OrganizationORCiD Member Organization
  • DataCiteDataCite
  • Re3DataRe3Data
  • OpenDOAROpenDOAR
  • OpenAireOpenAire
  • BASE Bielefeld Academic Search EngineBASE Bielefeld Academic Search Engine
Feedback