Benvenuti nell'Anagrafe della Ricerca d'Ateneo
La valutazione delle attività di ricerca che si svolgono nelle università ha assunto un'importanza rilevante sia per l'intero sistema universitario sia all'interno di ogni singolo ateneo. Roma Tre si è quindi dotata di idonei strumenti informativi in grado di supportare al meglio le azioni di monitoraggio e di valutazione delle attività di ricerca svolte nei propri dipartimentied ha realizzato una Anagrafe della Ricerca di Ateneo.
EnglishA long-standing conjecture by Heath, Pemmaraju, and Trenk states that the upward book thickness of outerplanar DAGs is bounded above by a constant. In this paper, we show that the conjecture holds for subfamilies of upward outerplanar graphs, namely those whose underlying graph is an internally-triangulated outerpath or a cactus, and those whose biconnected components are st-outerplanar graphs. On the complexity side, it is known that deciding whether a graph has upward book thickness k is NP-hard for any fixed k≥ 3. We show that the problem, for any k≥ 5, remains NP-hard for graphs whose domination number is O(k), but it is FPT in the vertex cover number.
Bhore, S., Da Lozzo, G., Montecchiani, F., & Nollenburg, M. (2021). On the Upward Book Thickness Problem: Combinatorial and Complexity Results. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.242-256). Springer Science and Business Media Deutschland GmbH [10.1007/978-3-030-92931-2_18].
| Titolo: | On the Upward Book Thickness Problem: Combinatorial and Complexity Results | |
| Autori: | ||
| Data di pubblicazione: | 2021 | |
| Serie: | ||
| Citazione: | Bhore, S., Da Lozzo, G., Montecchiani, F., & Nollenburg, M. (2021). On the Upward Book Thickness Problem: Combinatorial and Complexity Results. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.242-256). Springer Science and Business Media Deutschland GmbH [10.1007/978-3-030-92931-2_18]. | |
| Handle: | http://hdl.handle.net/11590/404544 | |
| Appare nelle tipologie: | 4.1 Contributo in Atti di convegno |
File in questo prodotto:
Copyright © 2022