Thumbnail

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
2020
Journal name
Algorithmica
Volume
82
Number
7
Publisher
Springer
Pages
1909–1938
Publication identifier
Metadata
Show full item record
Author(s)
Hanaka, Tesshu
Katsikarelis, Ioannis
Lampis, Michael cc
Otachi, Yota
Sikora, Florian cc
Abstract (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; SETH