The cost of hyperpaths in directed hypergraphs can be measuread in various different ways, which have been used in a wide set of applications. Not surprisingly, depending on the considered measure function the cost to find optimum hyperpaths may range from NP-hard to linear time. A first solution for finding optimum hyperpaths in case of a superior functions (SUP) can be found in a seminal work by Knuth [5], which generalizes Dijkstra’s Algorithm [3] to deal with a grammar problem. In this paper we define a hierarchy of classes of optimization problems based on the properties of the cost measures. After showing that measures can be classified on the basis of the structure of the optimum hyperpath they determine, we present an alternative taxonomy of measure functions, based on their analytic properties, and prove structure theorems that relate the two hierarchies.

Structure theorems for optimum hyperpaths in directed hypergraphs

LAURA, Luigi;
2012-01-01

Abstract

The cost of hyperpaths in directed hypergraphs can be measuread in various different ways, which have been used in a wide set of applications. Not surprisingly, depending on the considered measure function the cost to find optimum hyperpaths may range from NP-hard to linear time. A first solution for finding optimum hyperpaths in case of a superior functions (SUP) can be found in a seminal work by Knuth [5], which generalizes Dijkstra’s Algorithm [3] to deal with a grammar problem. In this paper we define a hierarchy of classes of optimization problems based on the properties of the cost measures. After showing that measures can be classified on the basis of the structure of the optimum hyperpath they determine, we present an alternative taxonomy of measure functions, based on their analytic properties, and prove structure theorems that relate the two hierarchies.
2012
978-3-642-32146-7
directed hypergraphs
hyperpath
File in questo prodotto:
File Dimensione Formato  
VE_2012_11573-759804.pdf

non disponibili

Dimensione 278.44 kB
Formato Adobe PDF
278.44 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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: https://hdl.handle.net/20.500.14086/377
 Attenzione

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

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