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.

Using Answer Set Programming to Find Maximum Height Spanning Trees

MANNA, MARCO
2013

Abstract

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.
Answer Set Programming; Declarative Problem Solving; Artificial Intelligence; Spanning Trees; Optimization Problems
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.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/20.500.11770/148599
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact