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
TypeArticle accepté pour publication ou publié
MetadataShow full item record
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 / KeywordsOrientation; Parameterization; Treewidth; SETH
Showing items related by title and author.