File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/s10878-011-9440-0
- Scopus: eid_2-s2.0-84878348719
- WOS: WOS:000319760900010
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Approximate min-max relations on plane graphs
| Title | Approximate min-max relations on plane graphs |
|---|---|
| Authors | |
| Keywords | Approximate min-max relation Cycle Feedback set Plane graph |
| Issue Date | 2013 |
| Publisher | Springer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905 |
| Citation | Journal Of Combinatorial Optimization, 2013, v. 26 n. 1, p. 127-134 How to Cite? |
| Abstract | Let G be a plane graph, let τ(G) (resp. τ′(G)) be the minimum number of vertices (resp. edges) that meet all cycles of G, and let ν(G) (resp. ν′(G)) be the maximum number of vertex-disjoint (resp. edge-disjoint) cycles in G. In this note we show that τ(G)≤3 ν(G) and τ′(G)≤4 ν′(G)-1; our proofs are constructive, which yield polynomial-time algorithms for finding corresponding objects with the desired properties. © 2011 The Author(s). |
| Persistent Identifier | http://hdl.handle.net/10722/147122 |
| ISSN | 2021 Impact Factor: 1.262 2020 SCImago Journal Rankings: 0.538 |
| ISI Accession Number ID | |
| References | Bondy JA, Murty USR (2008) Graph Theory. Springer, Berlin doi: 10.1007/978-1-84628-970-5 Erdős P, Pósa L (1965) On independent circuits contained in a graph. Canad J Math 17:347–352 doi: 10.4153/CJM-1965-035-8 Fiorini S, Hardy N, Reed B, Vetta A (2007) Approximate min-max relations for odd cycles in planar graphs. Math Program Ser B 110:71–91 doi: 10.1007/s10107-006-0063-7 Král D, Voss H-J (2004) Edge-disjoint odd cycles in planar graphs. J Combin Theory Ser B 90:107–120 doi: 10.1016/S0095-8956(03)00078-9 Lucchesi C, Younger D (1978) A minimax theorem for directed graphs. J London Math Soc 17:369–374 doi: 10.1112/jlms/s2-17.3.369 Reed B, Shepherd F (1996) The Gallai-Younger conjecture for planar graphs. Combinatorica 16:555–566 doi: 10.1007/BF01271273 Reed B, Robertson N, Seymour P, Thomas R (1996) Packing directed circuits. Combinatorica 16:535–554 doi: 10.1007/BF01271272 |
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Ma, J | en_HK |
| dc.contributor.author | Yu, X | en_HK |
| dc.contributor.author | Zang, W | en_HK |
| dc.date.accessioned | 2012-05-28T08:19:02Z | - |
| dc.date.available | 2012-05-28T08:19:02Z | - |
| dc.date.issued | 2013 | en_HK |
| dc.identifier.citation | Journal Of Combinatorial Optimization, 2013, v. 26 n. 1, p. 127-134 | en_HK |
| dc.identifier.issn | 1382-6905 | en_HK |
| dc.identifier.uri | http://hdl.handle.net/10722/147122 | - |
| dc.description.abstract | Let G be a plane graph, let τ(G) (resp. τ′(G)) be the minimum number of vertices (resp. edges) that meet all cycles of G, and let ν(G) (resp. ν′(G)) be the maximum number of vertex-disjoint (resp. edge-disjoint) cycles in G. In this note we show that τ(G)≤3 ν(G) and τ′(G)≤4 ν′(G)-1; our proofs are constructive, which yield polynomial-time algorithms for finding corresponding objects with the desired properties. © 2011 The Author(s). | en_HK |
| dc.language | eng | en_US |
| dc.publisher | Springer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905 | en_HK |
| dc.relation.ispartof | Journal of Combinatorial Optimization | en_HK |
| dc.rights | The Author(s) | en_US |
| dc.rights | This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License. | en_US |
| dc.subject | Approximate min-max relation | en_HK |
| dc.subject | Cycle | en_HK |
| dc.subject | Feedback set | en_HK |
| dc.subject | Plane graph | en_HK |
| dc.title | Approximate min-max relations on plane graphs | en_HK |
| dc.type | Article | en_HK |
| dc.identifier.openurl | http://www.springerlink.com/link-out/?id=2104&code=M022GU5270P8337R&MUD=MP | en_US |
| dc.identifier.email | Zang, W:wzang@maths.hku.hk | en_HK |
| dc.identifier.authority | Zang, W=rp00839 | en_HK |
| dc.description.nature | published_or_final_version | en_US |
| dc.identifier.doi | 10.1007/s10878-011-9440-0 | en_HK |
| dc.identifier.scopus | eid_2-s2.0-84878348719 | en_HK |
| dc.identifier.hkuros | 222187 | - |
| dc.relation.references | Bondy JA, Murty USR (2008) Graph Theory. Springer, Berlin | en_US |
| dc.relation.references | doi: 10.1007/978-1-84628-970-5 | en_US |
| dc.relation.references | Erdős P, Pósa L (1962) On the maximal number of disjoint circuits of a graph. Publ Math Debrecen 9:3–12 | en_US |
| dc.relation.references | Erdős P, Pósa L (1965) On independent circuits contained in a graph. Canad J Math 17:347–352 | en_US |
| dc.relation.references | doi: 10.4153/CJM-1965-035-8 | en_US |
| dc.relation.references | Fiorini S, Hardy N, Reed B, Vetta A (2007) Approximate min-max relations for odd cycles in planar graphs. Math Program Ser B 110:71–91 | en_US |
| dc.relation.references | doi: 10.1007/s10107-006-0063-7 | en_US |
| dc.relation.references | Kloks T, Lee CM, Liu J (2007) Jones’ conjecture. Open Problems Garden (see: http://garden.irmacs.sfu.ca/?q=category/graph_theory) | en_US |
| dc.relation.references | Král D, Voss H-J (2004) Edge-disjoint odd cycles in planar graphs. J Combin Theory Ser B 90:107–120 | en_US |
| dc.relation.references | doi: 10.1016/S0095-8956(03)00078-9 | en_US |
| dc.relation.references | Lucchesi C, Younger D (1978) A minimax theorem for directed graphs. J London Math Soc 17:369–374 | en_US |
| dc.relation.references | doi: 10.1112/jlms/s2-17.3.369 | en_US |
| dc.relation.references | Reed B, Shepherd F (1996) The Gallai-Younger conjecture for planar graphs. Combinatorica 16:555–566 | en_US |
| dc.relation.references | doi: 10.1007/BF01271273 | en_US |
| dc.relation.references | Reed B, Robertson N, Seymour P, Thomas R (1996) Packing directed circuits. Combinatorica 16:535–554 | en_US |
| dc.relation.references | doi: 10.1007/BF01271272 | en_US |
| dc.relation.references | Albertson M, Berman D (1979) A conjecture on planar graphs. In: Bondy JA, Murty USR (eds) Graph theory and related topics. Academic Press, San Diego, p 357 | en_US |
| dc.relation.references | Kloks T, Lee CM, Liu J (2002) New algorithms for k-face cover, k-feedback vertex set, and k-disjoint cycles on plane and planar graphs. In: Lecture notes in comput sci, vol 2573, pp 282–295 | en_US |
| dc.relation.references | Younger D (1973) Graphs with interlinked directed circuits. In: Proceedings of IEEE 16th Midwest symposium on circuit theory, vol 2, pp 2.1–2.7 | en_US |
| dc.identifier.spage | 127 | en_HK |
| dc.identifier.epage | 134 | en_HK |
| dc.identifier.eissn | 1573-2886 | en_US |
| dc.identifier.isi | WOS:000319760900010 | - |
| dc.publisher.place | Netherlands | en_HK |
| dc.description.other | Springer Open Choice, 28 May 2012 | en_US |
| dc.identifier.scopusauthorid | Ma, J=35792514200 | en_HK |
| dc.identifier.scopusauthorid | Yu, X=7404115058 | en_HK |
| dc.identifier.scopusauthorid | Zang, W=7005740804 | en_HK |
| dc.identifier.citeulike | 10163340 | - |
| dc.identifier.issnl | 1382-6905 | - |