File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Differential methods for finding independent sets in hypergraphs

TitleDifferential methods for finding independent sets in hypergraphs
Authors
Li, YZang, W
KeywordsAlgorithm
Convex function
Differential method
Hypergraph
Independent set
Issue Date2006
PublisherSociety 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?
DOI: http://dx.doi.org/10.1137/S0895480104442571
AbstractIt 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 Identifierhttp://hdl.handle.net/10722/44906
ISSN
0895-4801
2021 Impact Factor: 0.868
2020 SCImago Journal Rankings: 0.843
ISI Accession Number ID
WOS:000236805400009
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorLi, Yen_HK
dc.contributor.authorZang, Wen_HK
dc.date.accessioned2007-10-30T06:13:08Z-
dc.date.available2007-10-30T06:13:08Z-
dc.date.issued2006en_HK
dc.identifier.citationSIAM Journal On Discrete Mathematics, 2006, v. 20 n. 1, p. 96-104en_HK
dc.identifier.issn0895-4801en_HK
dc.identifier.urihttp://hdl.handle.net/10722/44906-
dc.description.abstractIt 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.extent148609 bytes-
dc.format.extent26112 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypeapplication/msword-
dc.languageengen_HK
dc.publisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sidma.php-
dc.relation.ispartofSIAM Journal on Discrete Mathematicsen_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.subjectAlgorithmen_HK
dc.subjectConvex functionen_HK
dc.subjectDifferential methoden_HK
dc.subjectHypergraphen_HK
dc.subjectIndependent seten_HK
dc.titleDifferential methods for finding independent sets in hypergraphsen_HK
dc.typeArticleen_HK
dc.identifier.emailZang, W:wzang@maths.hku.hken_HK
dc.identifier.authorityZang, W=rp00839en_HK
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.doi10.1137/S0895480104442571en_HK
dc.identifier.scopuseid_2-s2.0-33847619876en_HK
dc.identifier.hkuros116080-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33847619876&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume20en_HK
dc.identifier.issue1en_HK
dc.identifier.spage96en_HK
dc.identifier.epage104en_HK
dc.identifier.isiWOS:000236805400009-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridLi, Y=7502087425en_HK
dc.identifier.scopusauthoridZang, W=7005740804en_HK
dc.identifier.issnl0895-4801-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats