File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A min-max theorem on feedback vertex sets

TitleA min-max theorem on feedback vertex sets
Authors
Cai, MCDeng, XZang, W
KeywordsApproximation algorithm
Bipartite tournament
Feedback vertex set
Min-max relation
Totally dual integrality
Issue Date2002
PublisherI N F O R M S. The Journal's web site is located at http://mor.pubs.informs.org
Citation
Mathematics Of Operations Research, 2002, v. 27 n. 2, p. 361-371 How to Cite?
AbstractWe establish a necessary and sufficient condition for the linear system {x : Hx ≥ e, x ≥ 0} associated with a bipartite tournament to be totally dual integral, where H is the cycle-vertex incidence matrix and e is the all-one vector. The consequence is a min-max relation on packing and covering cycles, together with strongly polynomial time algorithms for the feedback vertex set problem and the cycle packing problem on the corresponding bipartite tournaments. In addition, we show that the feedbank vertex set problem on general bipartite tournaments is NP-complete and approximable within 3.5 based on the min-max theorem.
Persistent Identifierhttp://hdl.handle.net/10722/75253
ISSN
0364-765X
2023 Impact Factor: 1.4
2023 SCImago Journal Rankings: 1.215
ISI Accession Number ID
WOS:000176534700008
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorCai, MCen_HK
dc.contributor.authorDeng, Xen_HK
dc.contributor.authorZang, Wen_HK
dc.date.accessioned2010-09-06T07:09:23Z-
dc.date.available2010-09-06T07:09:23Z-
dc.date.issued2002en_HK
dc.identifier.citationMathematics Of Operations Research, 2002, v. 27 n. 2, p. 361-371en_HK
dc.identifier.issn0364-765Xen_HK
dc.identifier.urihttp://hdl.handle.net/10722/75253-
dc.description.abstractWe establish a necessary and sufficient condition for the linear system {x : Hx ≥ e, x ≥ 0} associated with a bipartite tournament to be totally dual integral, where H is the cycle-vertex incidence matrix and e is the all-one vector. The consequence is a min-max relation on packing and covering cycles, together with strongly polynomial time algorithms for the feedback vertex set problem and the cycle packing problem on the corresponding bipartite tournaments. In addition, we show that the feedbank vertex set problem on general bipartite tournaments is NP-complete and approximable within 3.5 based on the min-max theorem.en_HK
dc.languageengen_HK
dc.publisherI N F O R M S. The Journal's web site is located at http://mor.pubs.informs.orgen_HK
dc.relation.ispartofMathematics of Operations Researchen_HK
dc.subjectApproximation algorithmen_HK
dc.subjectBipartite tournamenten_HK
dc.subjectFeedback vertex seten_HK
dc.subjectMin-max relationen_HK
dc.subjectTotally dual integralityen_HK
dc.titleA min-max theorem on feedback vertex setsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0364-765X&volume=27&spage=361&epage=371&date=2002&atitle=A+Min-Max+Theorem+on+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-0036577366en_HK
dc.identifier.hkuros66885en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0036577366&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume27en_HK
dc.identifier.issue2en_HK
dc.identifier.spage361en_HK
dc.identifier.epage371en_HK
dc.identifier.isiWOS:000176534700008-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridCai, MC=7202863434en_HK
dc.identifier.scopusauthoridDeng, X=7401768881en_HK
dc.identifier.scopusauthoridZang, W=7005740804en_HK
dc.identifier.issnl0364-765X-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats