File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1137/S0895480104442571
- Scopus: eid_2-s2.0-33847619876
- WOS: WOS:000236805400009
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Differential methods for finding independent sets in hypergraphs
Title | Differential methods for finding independent sets in hypergraphs |
---|---|
Authors | |
Keywords | Algorithm Convex function Differential method Hypergraph Independent set |
Issue Date | 2006 |
Publisher | Society for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sidma.php |
Citation | SIAM Journal On Discrete Mathematics, 2006, v. 20 n. 1, p. 96-104 How to Cite? |
Abstract | It is shown by using differential methods that if H is a double linear, r-uniform hypergraph with degree sequence {dv} such that any subhypergraph induced by a neighborhood has maximum degree less than m, then its independence number is at least Σvfr,m(dv), where fr,m(x) is a convex function satisfying fr,m(x) ∼ (logx)/x if r = 2 and c/x1/(r-1) if r ≥ 3, as x → ∞, and c = c(r, m) > 0 is a constant. The proof yields a polynomial-time algorithm for finding such an independent set in H. © 2006 Society for Industrial and Applied Mathematics. |
Persistent Identifier | http://hdl.handle.net/10722/44906 |
ISSN | 2023 Impact Factor: 0.9 2023 SCImago Journal Rankings: 1.031 |
ISI Accession Number ID | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Li, Y | en_HK |
dc.contributor.author | Zang, W | en_HK |
dc.date.accessioned | 2007-10-30T06:13:08Z | - |
dc.date.available | 2007-10-30T06:13:08Z | - |
dc.date.issued | 2006 | en_HK |
dc.identifier.citation | SIAM Journal On Discrete Mathematics, 2006, v. 20 n. 1, p. 96-104 | en_HK |
dc.identifier.issn | 0895-4801 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/44906 | - |
dc.description.abstract | It is shown by using differential methods that if H is a double linear, r-uniform hypergraph with degree sequence {dv} such that any subhypergraph induced by a neighborhood has maximum degree less than m, then its independence number is at least Σvfr,m(dv), where fr,m(x) is a convex function satisfying fr,m(x) ∼ (logx)/x if r = 2 and c/x1/(r-1) if r ≥ 3, as x → ∞, and c = c(r, m) > 0 is a constant. The proof yields a polynomial-time algorithm for finding such an independent set in H. © 2006 Society for Industrial and Applied Mathematics. | en_HK |
dc.format.extent | 148609 bytes | - |
dc.format.extent | 26112 bytes | - |
dc.format.mimetype | application/pdf | - |
dc.format.mimetype | application/msword | - |
dc.language | eng | en_HK |
dc.publisher | Society for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sidma.php | - |
dc.relation.ispartof | SIAM Journal on Discrete Mathematics | en_HK |
dc.rights | © 2006 Society for Industrial and Applied Mathematics. First Published in SIAM Journal on Discrete Mathematics in volume 20, issue 1, published by the Society for Industrial and Applied Mathematics (SIAM). | - |
dc.subject | Algorithm | en_HK |
dc.subject | Convex function | en_HK |
dc.subject | Differential method | en_HK |
dc.subject | Hypergraph | en_HK |
dc.subject | Independent set | en_HK |
dc.title | Differential methods for finding independent sets in hypergraphs | en_HK |
dc.type | Article | en_HK |
dc.identifier.email | Zang, W:wzang@maths.hku.hk | en_HK |
dc.identifier.authority | Zang, W=rp00839 | en_HK |
dc.description.nature | published_or_final_version | en_HK |
dc.identifier.doi | 10.1137/S0895480104442571 | en_HK |
dc.identifier.scopus | eid_2-s2.0-33847619876 | en_HK |
dc.identifier.hkuros | 116080 | - |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-33847619876&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 20 | en_HK |
dc.identifier.issue | 1 | en_HK |
dc.identifier.spage | 96 | en_HK |
dc.identifier.epage | 104 | en_HK |
dc.identifier.isi | WOS:000236805400009 | - |
dc.publisher.place | United States | en_HK |
dc.identifier.scopusauthorid | Li, Y=7502087425 | en_HK |
dc.identifier.scopusauthorid | Zang, W=7005740804 | en_HK |
dc.identifier.issnl | 0895-4801 | - |