The minimum number of e-vertex-covers among hypergraphs with e edges of given ranks

F. H. Chang; Hung-Lin Fu; F. K. Hwang; B. C. Lin

doi:10.1016/j.dam.2008.05.006

The minimum number of e-vertex-covers among hypergraphs with e edges of given ranks

F. H. Chang^*, Hung-Lin Fu, F. K. Hwang, B. C. Lin

^*Corresponding author for this work

Department of Applied Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

We study the problem that among all hypergraphs with e edges of ranks l₁, ..., l_e and v vertices, which hypergraph has the least number of vertex-covers of size e. The problem is very difficult and we only get some partial answers. We show an application of our results to improve the error-tolerance of a pooling design proposed in the literature.

Original language	English
Pages (from-to)	164-169
Number of pages	6
Journal	Discrete Applied Mathematics
Volume	157
Issue number	1
DOIs	https://doi.org/10.1016/j.dam.2008.05.006
State	Published - 6 Jan 2009

Keywords

Hypergraph
Pooling design
Vertex-cover

Access to Document

10.1016/j.dam.2008.05.006

Fingerprint Dive into the research topics of 'The minimum number of e-vertex-covers among hypergraphs with e edges of given ranks'. Together they form a unique fingerprint.

Cite this

@article{bd14a640d3c445129c119491cf6a399c,

title = "The minimum number of e-vertex-covers among hypergraphs with e edges of given ranks",

abstract = "We study the problem that among all hypergraphs with e edges of ranks l1, ..., le and v vertices, which hypergraph has the least number of vertex-covers of size e. The problem is very difficult and we only get some partial answers. We show an application of our results to improve the error-tolerance of a pooling design proposed in the literature.",

keywords = "Hypergraph, Pooling design, Vertex-cover",

author = "Chang, {F. H.} and Hung-Lin Fu and Hwang, {F. K.} and Lin, {B. C.}",

year = "2009",

month = jan,

day = "6",

doi = "10.1016/j.dam.2008.05.006",

language = "English",

volume = "157",

pages = "164--169",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - The minimum number of e-vertex-covers among hypergraphs with e edges of given ranks

AU - Chang, F. H.

AU - Fu, Hung-Lin

AU - Hwang, F. K.

AU - Lin, B. C.

PY - 2009/1/6

Y1 - 2009/1/6

N2 - We study the problem that among all hypergraphs with e edges of ranks l1, ..., le and v vertices, which hypergraph has the least number of vertex-covers of size e. The problem is very difficult and we only get some partial answers. We show an application of our results to improve the error-tolerance of a pooling design proposed in the literature.

AB - We study the problem that among all hypergraphs with e edges of ranks l1, ..., le and v vertices, which hypergraph has the least number of vertex-covers of size e. The problem is very difficult and we only get some partial answers. We show an application of our results to improve the error-tolerance of a pooling design proposed in the literature.

KW - Hypergraph

KW - Pooling design

KW - Vertex-cover

UR - http://www.scopus.com/inward/record.url?scp=56349167900&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2008.05.006

DO - 10.1016/j.dam.2008.05.006

M3 - Article

AN - SCOPUS:56349167900

VL - 157

SP - 164

EP - 169

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 1

ER -