Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2016) | last year (2015) | two years ago (2014) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




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, 07/15/2014
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)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
02/22/2005 07:03:32 PM
Revisions
3.
2.
1.
0.
Editor(s)
Christine Kiesel
Christine Kiesel
Khaled Elbassioni
Khaled Elbassioni
Edit Dates
02.05.2007 15:40:34
02.05.2007 15:40:24
04/20/2006 06:42:08 PM
02/22/2005 07:03:32 PM