File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A min-max relation on packing feedback vertex sets

TitleA min-max relation on packing feedback vertex sets
Authors
Chen, XDing, GHu, XZang, W
KeywordsClutter
Covering
Feedback Vertex Set
Min-Max Relation
Packing
Issue Date2006
PublisherINFORMS. The Journal's web site is located at http://mor.pubs.informs.org
Citation
Mathematics Of Operations Research, 2006, v. 31 n. 4, p. 777-788 How to Cite?
DOI: http://dx.doi.org/10.1287/moor.1060.0200
AbstractLet G be a graph with a nonnegative integral function w defined on V(G). A collection f of subsets of V(G) (repetition is allowed) is called a feedback vertex set packing in G if the removal of any member of f from G leaves a forest, and every vertex v ∈ V(G) is contained in at most w(v) members of f The weight of a cycle C in G is the sum of w(v), over all vertices v of C. The purpose of this paper is to characterize all graphs with the property that, for any nonnegative integral function w, the maximum cardinality of a feedback vertex set packing is equal to the minimum weight of a cycle. © 2006 INFORMS.
Persistent Identifierhttp://hdl.handle.net/10722/156180
ISSN
0364-765X
2023 Impact Factor: 1.4
2023 SCImago Journal Rankings: 1.215
ISI Accession Number ID
WOS:000243230800008
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorChen, Xen_US
dc.contributor.authorDing, Gen_US
dc.contributor.authorHu, Xen_US
dc.contributor.authorZang, Wen_US
dc.date.accessioned2012-08-08T08:40:44Z-
dc.date.available2012-08-08T08:40:44Z-
dc.date.issued2006en_US
dc.identifier.citationMathematics Of Operations Research, 2006, v. 31 n. 4, p. 777-788en_US
dc.identifier.issn0364-765Xen_US
dc.identifier.urihttp://hdl.handle.net/10722/156180-
dc.description.abstractLet G be a graph with a nonnegative integral function w defined on V(G). A collection f of subsets of V(G) (repetition is allowed) is called a feedback vertex set packing in G if the removal of any member of f from G leaves a forest, and every vertex v ∈ V(G) is contained in at most w(v) members of f The weight of a cycle C in G is the sum of w(v), over all vertices v of C. The purpose of this paper is to characterize all graphs with the property that, for any nonnegative integral function w, the maximum cardinality of a feedback vertex set packing is equal to the minimum weight of a cycle. © 2006 INFORMS.en_US
dc.languageengen_US
dc.publisherINFORMS. The Journal's web site is located at http://mor.pubs.informs.orgen_US
dc.relation.ispartofMathematics of Operations Researchen_US
dc.subjectClutteren_US
dc.subjectCoveringen_US
dc.subjectFeedback Vertex Seten_US
dc.subjectMin-Max Relationen_US
dc.subjectPackingen_US
dc.titleA min-max relation on packing feedback vertex setsen_US
dc.typeArticleen_US
dc.identifier.emailZang, W:wzang@maths.hku.hken_US
dc.identifier.authorityZang, W=rp00839en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1287/moor.1060.0200en_US
dc.identifier.scopuseid_2-s2.0-33847230189en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33847230189&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume31en_US
dc.identifier.issue4en_US
dc.identifier.spage777en_US
dc.identifier.epage788en_US
dc.identifier.isiWOS:000243230800008-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridChen, X=8987182300en_US
dc.identifier.scopusauthoridDing, G=7201791806en_US
dc.identifier.scopusauthoridHu, X=35279969700en_US
dc.identifier.scopusauthoridZang, W=7005740804en_US
dc.identifier.citeulike1468222-
dc.identifier.issnl0364-765X-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats