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
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://epubs.siam.org/sam-bin/dbq/toclist/SIDMA
Citation
SIAM Journal On Discrete Mathematics, 2006, v. 20 n. 1, p. 96-104 How to Cite?
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
2015 Impact Factor: 0.793
2015 SCImago Journal Rankings: 1.230
ISI Accession Number ID
References

 

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://epubs.siam.org/sam-bin/dbq/toclist/SIDMAen_HK
dc.relation.ispartofSIAM Journal on Discrete Mathematicsen_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
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.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0895-4801&volume=20&issue=1&spage=96&epage=104&date=2006&atitle=Differential+methods+for+finding+independent+sets+in+hypergraphsen_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

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats