
Parameterized Orientable Deletion
Hanaka, Tesshu; Katsikarelis, Ioannis; Lampis, Michael; Otachi, Yota; Sikora, Florian (2020), Parameterized Orientable Deletion, Algorithmica, 82, 7, p. 1909–1938. 10.1007/s00453-020-00679-6
View/ Open
Type
Article accepté pour publication ou publiéDate
2020Journal name
AlgorithmicaVolume
82Number
7Publisher
Springer
Pages
1909–1938
Publication identifier
Metadata
Show full item recordAbstract (EN)
A graph is d-orientable if its edges can be oriented so that the maximum in-degree of the resulting digraph is at most d. d-orientability is a well-studied concept with close connections to fundamental graph-theoretic notions and applications as a load balancing problem. In this paper we consider the d-ORIENTABLE DELETION problem: given a graph G=(V,E), delete the minimum number of vertices to make Gd-orientable. We contribute a number of results that improve the state of the art on this problem.Subjects / Keywords
Orientation; Parameterization; Treewidth; SETHRelated items
Showing items related by title and author.
-
Hanaka, Tesshu; Katsikarelis, Ioannis; Lampis, Michael; Otachi, Yota; Sikora, Florian (2018) Communication / Conférence
-
Belmonte, Rémy; Hanaka, Tesshu; Katsikarelis, Ioannis; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2019) Communication / Conférence
-
Belmonte, Rémy; Hanaka, Tesshu; Katsikarelis, Ioannis; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2019) Article accepté pour publication ou publié
-
Belmonte, Rémy; Hanaka, Tesshu; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2019) Communication / Conférence
-
Belmonte, Rémy; Hanaka, Tesshu; Lampis, Michael; Ono, Hirotaka; Otachi, Yota (2020) Article accepté pour publication ou publié