×

Finding an induced path of given parity in planar graphs in polynomial time. (English) Zbl 1423.68342

Rabani, Yuval (ed.), Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 656-670 (2012).

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: Link

References:

[1] E. M. Arkin , C. H. Papadimitriou , M. Yannakakis, Modularity of cycles and paths in graphs, Journal of the ACM (JACM), v.38 n.2, p.255-274, April 1991 [doi>10.1145/103516.103517] · Zbl 0799.68146
[2] Srinivasa R. Arikati , Uri N. Peled, A linear algorithm for the group path problem on chordal graphs, Discrete Applied Mathematics, v.44 n.1-3, p.185-190, July 19, 1993 [doi>10.1016/0166-218X(93)90230-L] · Zbl 0779.68067 · doi:10.1016/0166-218X(93)90230-L
[3] Srinivasa R. Arikati , Uri N. Peled, A polynomial algorithm for the parity path problem on perfectly orientable graphs, Discrete Applied Mathematics, v.65 n.1-3, p.5-20, March 7, 1996 [doi>10.1016/0166-218X(95)00086-7] · Zbl 0854.68069 · doi:10.1016/0166-218X(95)00086-7
[4] Srinivasa R. Arikati , C. Pandu Rangan , Glenn K. Manacher, Efficient reduction for path problems on circular-arc graphs, BIT, v.31 n.2, p.182-193, 1991 · Zbl 0726.68059
[5] Dan Bienstock, On the complexity of testing for odd holes and induced odd paths, Discrete Mathematics, v.90 n.1, p.85-92, June 1991 [doi>10.1016/0012-365X(91)90098-M] · Zbl 0753.05046 · doi:10.1016/0012-365X(91)90098-M
[6] Hans L. Bodlaender, A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth, SIAM Journal on Computing, v.25 n.6, p.1305-1317, Dec. 1996 [doi>10.1137/S0097539793251219] · Zbl 0864.68074 · doi:10.1137/S0097539793251219
[7] Bruno Courcelle, The monadic second-order logic of graphs. I. recognizable sets of finite graphs, Information and Computation, v.85 n.1, p.12-75, March 1990 [doi>10.1016/0890-5401(90)90043-H] · Zbl 0722.03008 · doi:10.1016/0890-5401(90)90043-H
[8] R. Diestel. Graph Theory. (3rd Edition). Springer-Verlag Heidelberg, 2005. · Zbl 1074.05001
[9] H. Everett, C. M. H. de Figueiredo, C. Linhares Sales, F. Maffray, O. Porto, B. A. Reed. Path parity and perfection. In: L. Ramirez-Alfonsin and B. A. Reed (Eds.), Perfect Graphs, Wiley, 67-92, 2001. · Zbl 0879.05053
[10] J. Fonlupt and J. P. Uhry. Transformations which preserve perfectness and H-perfectness of graphs. Annals of Discrete Mathematics, 16:83-85, 1982. · Zbl 0502.05023
[11] Qian-Ping Gu , Hisao Tamaki, Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n^1 + ε) Time, Proceedings of the 20th International Symposium on Algorithms and Computation, p.984-993, December 16-18, 2009, Honolulu, Hawaii [doi>10.1007/978-3-642-10631-6_99] · Zbl 1272.05200 · doi:10.1007/978-3-642-10631-6_99
[12] Chính T. Hoàng , Van Bang Le, Recognizing Perfect 2-Split Graphs, SIAM Journal on Discrete Mathematics, v.13 n.1, p.48-55, Jan. 2000 [doi>10.1137/S0895480197329089] · Zbl 0946.05042 · doi:10.1137/S0895480197329089
[13] Pim Hof , Marcin Kamiński , Daniël Paulusma, Finding Induced Paths of Given Parity in Claw-Free Graphs, Graph-Theoretic Concepts in Computer Science: 35th International Workshop, WG 2009, Montpellier, France, June 24-26, 2009. Revised Papers, Springer-Verlag, Berlin, Heidelberg, 2009 [doi>10.1007/978-3-642-11409-0_30] · Zbl 1273.05224 · doi:10.1007/978-3-642-11409-0_30
[14] Wen-Lian Hsu, Recognizing planar perfect graphs, Journal of the ACM (JACM), v.34 n.2, p.255-288, April 1987 [doi>10.1145/23005.31330]
[15] Ken-Ichi Kawarabayashi , Yusuke Kobayashi, The induced disjoint paths problem, Proceedings of the 13th international conference on Integer programming and combinatorial optimization, May 26-28, 2008, Bertinoro, Italy · Zbl 1143.90379
[16] Ken-ichi Kawarabayashi , Bruce Reed , Paul Wollan, The Graph Minor Algorithm with Parity Conditions, Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, p.27-36, October 22-25, 2011 [doi>10.1109/FOCS.2011.52] · Zbl 1292.68127 · doi:10.1109/FOCS.2011.52
[17] A. S. LaPaugh and C. H. Papadimitriou. The even-path problem for graphs and digraphs. Networks, 14:507-513, 1984. · Zbl 0552.68059
[18] H. Meyniel, A new property of critical imperfect graphs and some consequences, European Journal of Combinatorics, v.8 n.3, p.313-316, July 1987 · Zbl 0647.05053
[19] B. Mohar and C. Thomassen. Graphs on Surfaces. The Johns Hopkins University Press, 2001. · Zbl 0979.05002
[20] Zhivko Prodanov Nedev, Finding an Even Simple Path in a Directed Planar Graph, SIAM Journal on Computing, v.29 n.2, p.685-695, Oct. 1999 [doi>10.1137/S0097539797330343] · Zbl 0939.68088 · doi:10.1137/S0097539797330343
[21] Neil Robertson , Paul Seymour , Robin Thomas, Quickly excluding a planar graph, Journal of Combinatorial Theory Series B, v.62 n.2, p.323-348, Nov. 1994 [doi>10.1006/jctb.1994.1073] · Zbl 0807.05023 · doi:10.1006/jctb.1994.1073
[22] C. L. Sales, F. Maffray and B. A. Reed. Recognizing planar strict quasi-parity graphs. Graphs and Combinatorics, 17(4): 745-757, 2001. · Zbl 0990.05052
[23] R. M. Sampaio and C. L. Sales. On the complexity of finding even pairs in planar perfect graphs. In: Brazilian Symposium on Graphs, Algorithms and Combinatorics 2001, Fortaleza, Electronic Notes in Discrete Mathematics, 7:186-189, 2001. · Zbl 0981.05048
[24] C. R. Satyan , C. Pandu Rangan, The parity path problem on some subclasses of perfect graphs, Discrete Applied Mathematics, v.68 n.3, p.293-302, July 24, 1996 [doi>10.1016/0166-218X(95)00065-Y] · Zbl 0859.05056 · doi:10.1016/0166-218X(95)00065-Y
[25] A. Tucker. The strong perfect graph conjecture for planar graphs. Canad. J. Math. 25:103- · Zbl 0251.05102
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.