The max tree-height of an undirected graph is the longest possible length of a path among all spanning trees of the graph. A maximum height spanning tree of an undirected graph is a spanning tree that has a path of length equal to the max tree-height of the graph. Finding the max tree-height of a graph, or similarly some spanning tree of maximum height, is an NP-hard optimization problem for which efficient optimal procedures have been proposed only for special classes of graphs, and which is not polynomially approximable within any constant factor unless PTIME = NP. The paper presents an elegant yet efficient and succinct logic program in Answer Set Programming for the identification of both the max tree-height and the maximum height spanning trees of a graph.
Using Answer Set Programming to Find Maximum Height Spanning Trees / Manna, Marco. - In: JOURNAL OF THEORETICAL AND APPLIED INFORMATION TECHNOLOGY. - ISSN 1992-8645. - 56:1(2013), pp. 146-152.
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
Titolo: | Using Answer Set Programming to Find Maximum Height Spanning Trees |
Autori: | |
Data di pubblicazione: | 2013 |
Rivista: | |
Citazione: | Using Answer Set Programming to Find Maximum Height Spanning Trees / Manna, Marco. - In: JOURNAL OF THEORETICAL AND APPLIED INFORMATION TECHNOLOGY. - ISSN 1992-8645. - 56:1(2013), pp. 146-152. |
Handle: | http://hdl.handle.net/20.500.11770/148599 |
Appare nelle tipologie: | 1.1 Articolo in rivista |