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

Voir/Ouvrir
Type
Article accepté pour publication ou publié
Date
2020
Nom de la revue
Algorithmica
Volume
82
Numéro
7
Éditeur
Springer
Pages
1909–1938
Identifiant publication
Métadonnées
Afficher la notice complète
Auteur(s)
Hanaka, Tesshu
Katsikarelis, Ioannis
Lampis, Michael cc
Otachi, Yota
Sikora, Florian cc
Résumé (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.
Mots-clés
Orientation; Parameterization; Treewidth; SETH