IRIS - Res&Arch Institutional Research Information System - Research & Archive
Anagrafe della Ricerca dell'Università degli Studi di Perugia.
EnglishThis paper presents an extensive study on the problem of computing maximum upward planar subgraphs of embedded planar digraphs: Complexity results, algorithms, and experiments are presented. Namely: (i) We prove that the addressed problem is NP-Hard; (ii) A fast heuristic and an exponential-time exact algorithm are described; (iii) A wide experimental analysis is performed to show the effectiveness of our techniques.
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
| Titolo: | Maximum Upward Planar Subgraphs of Embedded Planar Digraphs |
| Autori: | |
| Data di pubblicazione: | 2008 |
| Abstract: | This paper presents an extensive study on the problem of computing maximum upward planar subgraphs of embedded planar digraphs: Complexity results, algorithms, and experiments are presented. Namely: (i) We prove that the addressed problem is NP-Hard; (ii) A fast heuristic and an exponential-time exact algorithm are described; (iii) A wide experimental analysis is performed to show the effectiveness of our techniques. |
| Handle: | http://hdl.handle.net/11391/31794 |
| ISBN: | 9783540775362 |
| Appare nelle tipologie: | 4.1 Contributo in Atti di convegno |
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
Copyright © 2020