Questo sito utilizza cookie di terze parti per inviarti pubblicità in linea con le tue preferenze. Se vuoi saperne di più clicca QUI 
Chiudendo questo banner, scorrendo questa pagina, cliccando su un link o proseguendo la navigazione in altra maniera, acconsenti all'uso dei cookie. OK

Covering edges of a hypergraph: complexity and applications

This thesis gives an overview of the edge covering problems in hypergraphs.
We explore the complexity properties of covering the edges of a hypergraph by subhypergraphs of different types. We consider the problem of covering by clique hypergraphs, split hypergraph, and threshold hypergraphs.
In total we prove NP-completness of 6 problems. We especially focus on the problem of covering by threshold hypergraphs, which has applications in the theory of machine learning. We give a reduction from the clique covering problem, so proving NP-hardness of this problem would imply NP-hardness of the problem of covering by threshold hypergraphs. Moreover, we propose a generalization of the concept of Dilworth number of a graph to hypergraphs.
We give a polynomial algorithm for the computation of this number. We prove that the Dilworth number gives an upper bound for some important parameters like the diameter and domination number of a hypergraph.

Mostra/Nascondi contenuto.
Chapter 1 Introduction 1.1 Motivation The complexity properties of the covering problems in graphs have been ex- tensively studied by many authors (see [GJ79] for a survey). In recent years, Aizenstein et al. [AHHP98] has proved that efficient learnability in one of the on-line learning models is related to the representation problem, e.g. to decide if a given Boolean formula in DNF has a representation of some type, for example as a union of k linearly separable functions. NP-hardness of representation problem for some concept class implies negative results for its efficient learnability in this model. Such results are given for many con- cept classes, however for an important concept class - the class of unions of two linearly separable functions, the status of the representation problem is unknown. The covering problem by threshold hypergraphs can be easily transformed to the representation problem of unions of two linearly separa- ble functions. This thesis focuses on the complexity properties of covering problems in hypergraphs. These problems were not explored elsewhere, and their applications to the learning theory are a good motivation for a deeper examination of these problems. 1.2 Summary of thesis contributions We prove NP-completness of the following covering problems for r-uniform hypergraphs: 9

International thesis/dissertation

Autore: Vladimir Repisky Contatta »

Composta da 53 pagine.


Questa tesi ha raggiunto 107 click dal 12/12/2008.


Consultata integralmente 2 volte.

Disponibile in PDF, la consultazione è esclusivamente in formato digitale.