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.
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 subgraph...s 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.