An efficient parallel algorithm for computing a large independent set in a planar graph. (English) Zbl 0731.68085
Summary: Let \(\alpha\) (G) denote the independence number of a graph G, that is the maximum number of pairwise independent vertices in G. We present a parallel algorithm that computes in a planar graph \(G=(V,E)\), an independent set \(I\subseteq V\) such that \(| I| \geq \alpha (G)/2\). The algorithm runs in time \(O(\log^ 2n)\) and requires a linear number of processors. This is achieved by defining a new set of reductions that can be executed “locally” and simultaneously; furthermore, it is shown that a constant fraction of the vertices in the graph are reducible. This is the best known approximation scheme when the number of processors available is linear; parallel implementation of known sequential algorithms requires many more processors.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68W15 | Distributed algorithms |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
References:
| [1] | Aho, A.; Hopcroft, J.; Ullman, J., The Design and Analysis of Computer Algorithms (1974), Reading, MA: Addison-Wesley, Reading, MA · Zbl 0326.68005 |
| [2] | Appel, K. I.; Haken, W., Every planar map is four colorable, Bull Amer. Math. Soc., 82, 711-712 (1976) · Zbl 0331.05106 · doi:10.1090/S0002-9904-1976-14122-5 |
| [3] | B. S. Baker, Approximation algorithms for NP-complete problems on planar graphs,Proc. 24th IEEE Symp. on Foundations of Computer Science, 1983, pp. 265-273. |
| [4] | Berge, C., Graphs and Hypergraphs (1973), Amsterdam: North-Holland, Amsterdam · Zbl 0254.05101 |
| [5] | Chiba, N.; Nishizeki, T.; Saito, N., A linear algorithm for five-coloring a planar graph, J. Algorithms, 2, 317-327 (1981) · Zbl 0478.05041 · doi:10.1016/0196-6774(81)90031-6 |
| [6] | N. Chiba, T. Nishizeki, N. Saito, An approximation algorithm for the maximum independent set problem on planar graphs,SIAM. J. Comput. (1982), 663-675. · Zbl 0492.68051 |
| [7] | Frederickson, G. N., On linear-time algorithms for five-coloring planar graphs, Inform. Process. Lett., 19, 219-224 (1984) · Zbl 0563.05023 · doi:10.1016/0020-0190(84)90056-5 |
| [8] | Garey, M. R.; Johnson, D. S., Computers and Intractability-a Guide to the Theory of NP-completeness (1979), New York: Freeman, New York · Zbl 0411.68039 |
| [9] | Garey, M. R.; Johnson, D. S.; Stockmayer, L., Some simplified NP-complete problems, Theoret. Comput. Sci., 1, 237-267 (1976) · Zbl 0338.05120 · doi:10.1016/0304-3975(76)90059-1 |
| [10] | Goldberg, A.; Poltkin, S.; Shannon, G., Parallel symmetry breaking in sparse graphs, SIAM J. Discrete Math., 1, 434-446 (1988) · Zbl 0671.05038 · doi:10.1137/0401044 |
| [11] | Hagerup, T.; Chrobak, M.; Diks, K., Optimal parallel 5-colouring of planar graphs, SIAM J. Comput., 18, 288-300 (1989) · Zbl 0688.68068 · doi:10.1137/0218020 |
| [12] | Hopcroft, J. E.; Tarjan, R. E., Efficient planarity testing, J. Assoc. Comput. Mach., 21, 549-568 (1974) · Zbl 0307.68025 |
| [13] | Lipton, R. J.; Tarjan, R. E., Applications of a planar separator theorem, SIAM J. Comput., 9, 615-627 (1980) · Zbl 0456.68077 · doi:10.1137/0209046 |
| [14] | D. Matula, Y. Shiloah, R. Tarjan, Two linear-time algorithms for five-coloring a planar graph, Technical Report No. STAN-CS-80-830, Department of Computer Science, Stanford University. |
| [15] | Naor, J., A fast parallel coloring of planar graphs with five colors, Inform. Process. Lett., 25, 51-53 (1987) · Zbl 0653.68069 · doi:10.1016/0020-0190(87)90092-5 |
| [16] | C. H. Papadimitriou, M. Yannakakis, Worst-case ratios for planar graphs and the method of induction on faces,Proc. 22nd IEEE Symp. on Foundations of Computer Science, 1981, pp. 358-363. |
| [17] | V. Ramachandran, J. Reif, An optimal parallel algorithm for graph planarity,Proc. 30th IEEE Symp. on Foundations of Computer Science, 1989, pp. 282-287. |
| [18] | Shannon, C. E., A theorem on colouring lines of a network, J. Math. Phys., 28, 148-151 (1949) · Zbl 0032.43203 |
| [19] | Williams, M. H., A linear algorithm for coloring planar graphs with five colors, Comput. J., 28, 1, 78-81 (1985) · Zbl 0556.68036 · doi:10.1093/comjnl/28.1.78 |
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.
