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
Issue Date2005
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2005, v. 3827 LNCS, p. 126-135 How to Cite?
AbstractLet G be a graph with a nonnegative integral function w defined on V(G). A family 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. In this paper we 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. © Springer-Verlag Berlin Heidelberg 2005.
Persistent Identifierhttp://hdl.handle.net/10722/75457
ISSN
0302-9743
2023 SCImago Journal Rankings: 0.606
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorChen, Xen_HK
dc.contributor.authorDing, Gen_HK
dc.contributor.authorHu, Xen_HK
dc.contributor.authorZang, Wen_HK
dc.date.accessioned2010-09-06T07:11:17Z-
dc.date.available2010-09-06T07:11:17Z-
dc.date.issued2005en_HK
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2005, v. 3827 LNCS, p. 126-135en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/75457-
dc.description.abstractLet G be a graph with a nonnegative integral function w defined on V(G). A family 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. In this paper we 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. © Springer-Verlag Berlin Heidelberg 2005.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_HK
dc.titleA min-max relation on packing feedback vertex setsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0364-765X&volume=31&spage=777&epage=788&date=2006&atitle=A+Min-Max+Relation+on+Packing+Feedback+Vertex+Setsen_HK
dc.identifier.emailZang, W:wzang@maths.hku.hken_HK
dc.identifier.authorityZang, W=rp00839en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.scopuseid_2-s2.0-33744959981en_HK
dc.identifier.hkuros125305en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33744959981&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume3827 LNCSen_HK
dc.identifier.spage126en_HK
dc.identifier.epage135en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridChen, X=8987182300en_HK
dc.identifier.scopusauthoridDing, G=7201791806en_HK
dc.identifier.scopusauthoridHu, X=21934107100en_HK
dc.identifier.scopusauthoridZang, W=7005740804en_HK
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats