Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2014) | last year (2013) | two years ago (2012) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Boros, Endre
Elbassioni, Khaled M.
Khachiyan, Leonid
Gurvich, Vladimir

dblp
dblp
dblp
dblp

Not MPG Author(s):

Boros, Endre
Gurvich, Vladimir
Khachiyan, Leonid

BibTeX cite key*:

Elbassioni2003b

Title

Title*:

Extending the Balas-Yu Bounds on the Number of Maximal Independent Sets in Graphs to Hypergraphs and Lattices

Journal

Journal Title*:

Mathematical Programming, Ser. B

Journal's URL:


Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Springer

Publisher's URL:


Publisher's
Address:


ISSN:


Vol, No, pp, Date

Volume*:

98

Number:

1-3

Publishing Date:

2003

Pages*:

14

Number of
VG Pages:


Page Start:

355

Page End:

368

Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

A result of Balas and Yu (1989) states that the number of maximal independent sets of a graph $G=(V,E)$ is
upper-bounded by $\delta^{p} + 1$, where $\delta$ is the number of pairs of vertices in $V$ at distance 2, and $p$ is the cardinality of a maximum induced matching in $G$.
In this paper, we give an extension of this result for hypergraphs, or more generally for subsets of vectors $\cB$ in a product of $n$ lattices $\cL=\cL_1\times\cdots\times\cL_n$, where the notion of an induced matching in $G$ is replaced by a certain mapping of elements of $\cB$ to the nodes of a binary tree $\bT$ in some special way. Precisely, for $\cB\subseteq\cL$, let
$\gamma=\gamma(\cB)$ be the number of leaves in the largest tree for which such a mapping exists, denote by $\cI(\cB)$ the set of maximal independent elements of $\cB$, and let $\alpha=|\cI(\cB)|$ and $\beta=|\cB|$. We show that $\alpha \le\max\{Q,\beta^{\log \gamma/c(2Q,\beta)}\}$, where
$c(\rho,\theta)$ is the unique positive root of the equation $2^c(\rho^{c/\log \theta}-1)=1$, and $Q=\sum_{i=1}^n|\cL_i|$.
In particular, our bound implies that $\alpha \le (2Q\beta)^{\log \gamma}$. We also give examples of hypergraphs with arbitrarily large $n$, $\alpha$ and $\beta$ for which $\alpha \ge \beta^{(1-o(1)) \log \gamma/c}$.

As an application, we get an upper bound on the number
of maximal infeasible sets for a polymatroid inequality in terms of the number of feasible sets. We further show that such a bound allows for the incrementally efficient generation of all minimal feasible solutions to a given system of polymatroid inequalities $f_1(X) \ge t_1,\ldots,f_m(X) \geq t_m$ with quasi-polynomially bounded right hand sides $t_1,\ldots,t_m$.

URL for the Abstract:


Categories,
Keywords:

Hypergraphs, lattices, polymatroid functions, enumeration algorithms

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Intranet

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{Elbassioni2003b,
AUTHOR = {Boros, Endre and Elbassioni, Khaled M. and Khachiyan, Leonid and Gurvich, Vladimir},
TITLE = {Extending the Balas-Yu Bounds on the Number of Maximal Independent Sets in Graphs to Hypergraphs and Lattices},
JOURNAL = {Mathematical Programming, Ser. B},
PUBLISHER = {Springer},
YEAR = {2003},
NUMBER = {1-3},
VOLUME = {98},
PAGES = {14},
}


Entry last modified by Christine Kiesel, 05/02/2007
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)