File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Approximate min-max relations on plane graphs

TitleApproximate min-max relations on plane graphs
Authors
KeywordsApproximate min-max relation
Cycle
Feedback set
Plane graph
Issue Date2013
PublisherSpringer 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?
AbstractLet 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 Identifierhttp://hdl.handle.net/10722/147122
ISSN
2023 Impact Factor: 0.9
2023 SCImago Journal Rankings: 0.370
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 FieldValueLanguage
dc.contributor.authorMa, Jen_HK
dc.contributor.authorYu, Xen_HK
dc.contributor.authorZang, Wen_HK
dc.date.accessioned2012-05-28T08:19:02Z-
dc.date.available2012-05-28T08:19:02Z-
dc.date.issued2013en_HK
dc.identifier.citationJournal Of Combinatorial Optimization, 2013, v. 26 n. 1, p. 127-134en_HK
dc.identifier.issn1382-6905en_HK
dc.identifier.urihttp://hdl.handle.net/10722/147122-
dc.description.abstractLet 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.languageengen_US
dc.publisherSpringer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905en_HK
dc.relation.ispartofJournal of Combinatorial Optimizationen_HK
dc.rightsThe Author(s)en_US
dc.rightsThis work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.en_US
dc.subjectApproximate min-max relationen_HK
dc.subjectCycleen_HK
dc.subjectFeedback seten_HK
dc.subjectPlane graphen_HK
dc.titleApproximate min-max relations on plane graphsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://www.springerlink.com/link-out/?id=2104&code=M022GU5270P8337R&MUD=MPen_US
dc.identifier.emailZang, W:wzang@maths.hku.hken_HK
dc.identifier.authorityZang, W=rp00839en_HK
dc.description.naturepublished_or_final_versionen_US
dc.identifier.doi10.1007/s10878-011-9440-0en_HK
dc.identifier.scopuseid_2-s2.0-84878348719en_HK
dc.identifier.hkuros222187-
dc.relation.referencesBondy JA, Murty USR (2008) Graph Theory. Springer, Berlinen_US
dc.relation.referencesdoi: 10.1007/978-1-84628-970-5en_US
dc.relation.referencesErdős P, Pósa L (1962) On the maximal number of disjoint circuits of a graph. Publ Math Debrecen 9:3–12en_US
dc.relation.referencesErdős P, Pósa L (1965) On independent circuits contained in a graph. Canad J Math 17:347–352en_US
dc.relation.referencesdoi: 10.4153/CJM-1965-035-8en_US
dc.relation.referencesFiorini S, Hardy N, Reed B, Vetta A (2007) Approximate min-max relations for odd cycles in planar graphs. Math Program Ser B 110:71–91en_US
dc.relation.referencesdoi: 10.1007/s10107-006-0063-7en_US
dc.relation.referencesKloks 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.referencesKrál D, Voss H-J (2004) Edge-disjoint odd cycles in planar graphs. J Combin Theory Ser B 90:107–120en_US
dc.relation.referencesdoi: 10.1016/S0095-8956(03)00078-9en_US
dc.relation.referencesLucchesi C, Younger D (1978) A minimax theorem for directed graphs. J London Math Soc 17:369–374en_US
dc.relation.referencesdoi: 10.1112/jlms/s2-17.3.369en_US
dc.relation.referencesReed B, Shepherd F (1996) The Gallai-Younger conjecture for planar graphs. Combinatorica 16:555–566en_US
dc.relation.referencesdoi: 10.1007/BF01271273en_US
dc.relation.referencesReed B, Robertson N, Seymour P, Thomas R (1996) Packing directed circuits. Combinatorica 16:535–554en_US
dc.relation.referencesdoi: 10.1007/BF01271272en_US
dc.relation.referencesAlbertson 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 357en_US
dc.relation.referencesKloks 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–295en_US
dc.relation.referencesYounger D (1973) Graphs with interlinked directed circuits. In: Proceedings of IEEE 16th Midwest symposium on circuit theory, vol 2, pp 2.1–2.7en_US
dc.identifier.spage127en_HK
dc.identifier.epage134en_HK
dc.identifier.eissn1573-2886en_US
dc.identifier.isiWOS:000319760900010-
dc.publisher.placeNetherlandsen_HK
dc.description.otherSpringer Open Choice, 28 May 2012en_US
dc.identifier.scopusauthoridMa, J=35792514200en_HK
dc.identifier.scopusauthoridYu, X=7404115058en_HK
dc.identifier.scopusauthoridZang, W=7005740804en_HK
dc.identifier.citeulike10163340-
dc.identifier.issnl1382-6905-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats