File Download
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Article: A min-max theorem on feedback vertex sets
Title | A min-max theorem on feedback vertex sets |
---|---|
Authors | |
Keywords | Approximation algorithm Bipartite tournament Feedback vertex set Min-max relation Totally dual integrality |
Issue Date | 2002 |
Publisher | I 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? |
Abstract | We 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 Identifier | http://hdl.handle.net/10722/75253 |
ISSN | 2021 Impact Factor: 2.215 2020 SCImago Journal Rankings: 1.619 |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Cai, MC | en_HK |
dc.contributor.author | Deng, X | en_HK |
dc.contributor.author | Zang, W | en_HK |
dc.date.accessioned | 2010-09-06T07:09:23Z | - |
dc.date.available | 2010-09-06T07:09:23Z | - |
dc.date.issued | 2002 | en_HK |
dc.identifier.citation | Mathematics Of Operations Research, 2002, v. 27 n. 2, p. 361-371 | en_HK |
dc.identifier.issn | 0364-765X | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/75253 | - |
dc.description.abstract | We 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.language | eng | en_HK |
dc.publisher | I N F O R M S. The Journal's web site is located at http://mor.pubs.informs.org | en_HK |
dc.relation.ispartof | Mathematics of Operations Research | en_HK |
dc.subject | Approximation algorithm | en_HK |
dc.subject | Bipartite tournament | en_HK |
dc.subject | Feedback vertex set | en_HK |
dc.subject | Min-max relation | en_HK |
dc.subject | Totally dual integrality | en_HK |
dc.title | A min-max theorem on feedback vertex sets | en_HK |
dc.type | Article | en_HK |
dc.identifier.openurl | http://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+Sets | en_HK |
dc.identifier.email | Zang, W:wzang@maths.hku.hk | en_HK |
dc.identifier.authority | Zang, W=rp00839 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.scopus | eid_2-s2.0-0036577366 | en_HK |
dc.identifier.hkuros | 66885 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-0036577366&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 27 | en_HK |
dc.identifier.issue | 2 | en_HK |
dc.identifier.spage | 361 | en_HK |
dc.identifier.epage | 371 | en_HK |
dc.publisher.place | United States | en_HK |
dc.identifier.scopusauthorid | Cai, MC=7202863434 | en_HK |
dc.identifier.scopusauthorid | Deng, X=7401768881 | en_HK |
dc.identifier.scopusauthorid | Zang, W=7005740804 | en_HK |
dc.identifier.issnl | 0364-765X | - |