Brenda S. Baker
- ~BAR-YEHUDA, R., AND EVEN, $. 1982. On approximating a vertex cover for planar graphs. In ~Proceedings of the 14th ACM Sympostum on Theory of Computing (San Francisco, Calif., May ~5-7). ACM, New York, pp. 303-309. Google Scholar
- ~BERMAN, F., JOHNSON, D. S., LEIGHTON, F. T., SHOR, P. W., AND SNYDER, L. 1990. Generalized ~planar matching. J. Algor. 11, 2, 153-184. Google Scholar
- ~BERMAN, F., LEIGHTON, F. T., AND SNYDER, L. 1982. Optimal tile salvage. VLSI Memo No. ~82-119. Massachusetts Institute of Technology, Cambridge, Mass.Google Scholar
- ~BIENSTOCK, D., AND MONMA, C. L. 1990. On the complexity of embedding planar grapha to ~minimize certain distance measures. Al$orithmica 5, 93-109.Google Scholar
- ~BuI, T. N., AND JONES, C. 1992. Finding optimal vertex separators in planar graphs with small ~separators. Comput. Sci. Dept., Pennsylvania State Univ., University Park, Pa.Google Scholar
- ~Bul, T. N., AND PECK, A. 1992. Partitioning planar graphs. SIAMJ. Comput. 21, 2, 203-215. Google Scholar
- ~CHIBA, N., NISHIZEKI, T., AND SAITO, N. 198i, Applications of the Lipton and Tarjan's planar ~separator theorem. J. bzf. Proc. 4, 4, 203-207,Google Scholar
- ~CHIBA, N., NISHiZEKI, T., AND SAITO, N. 1982, An approximation algorithm for the maximum ~independent set problem on planar graphs. SIAM J. Comput. 11, 4, 663-675.Google Scholar
- ~COCKAYNE, E., GOODMAN, S., AND HEDETNIEMI, S. 1975. A linear algorithm for the domination ~number of a tree. Inf. Proc. Lett. 4, 41-44,Google Scholar
- ~DJIDJEV, H. N. 1982. On the problem of partitioning planar graphs. SIAM J. Alg. Dzsc. Meth. 3, ~2, 229-240.Google Scholar
- DOLEV, D., LEIGHTON, F., AND TRICKEY, H. 1984. Planar embedding of planar graphs. In ~Advances m Computing Research. Vol. I{: ~ZSI Theory (F. Preparata, ed.) JAI Press, Inc., ~Greenwich, Ct., pp. 147-161.Google Scholar
- ~GAREY, M. R., AND JOHNSON, D. S. 1979. Computers and Intractabihty, A Guide to the Theory of ~NP-Completeness. W. H. Freeman and Co., San Francisco, Calif. Google Scholar
- ~G^VRIL, F. 1972. Algorithms for minimum coloring, maximum clique, mimmum covering by ~cliques, and maximum independent set of a chordal graph. SIAMJ. Comput. l, 2, 180-187.Google Scholar
- ~HARARY, F. 1971. Graph Theory. Addison-Wesley, Reading, Mass.Google Scholar
- ~HOCHBAUM, D. S. 1981. Efficient bounds for the stable set, vertex cover and set packing ~problems. W.P. #50-80-81. GSIA, Carnegie-Mellon University, Pittsburgh, Pa., May.Google Scholar
- ~HOPCROFT, J. AND TARJAN, R. 1974. Efficient planarity testing. J. ACM 21 549-568. Google Scholar
- ~LIPTON, R. J., AND TARJAN, R. E. 1979. A separator theorem for planar graphs. SIAM J. Appl. ~Math. 36, 2, 177-189.Google Scholar
- ~LIPTON, R. J., AND TARJAN, R. E. 1980. Applications of a planar separator theorem. SIAM J. ~Comput. 9, 3, 615-627Google Scholar
- ~MrICHELL, S. 1977. Algorithms on trees and maximal outerplanar graphs: design, complexity ~analysis, and data structures study. Ph.D. dissertation. Univ. Virginia, Charlottesville, Va. Google Scholar
- ~MITCHELL, S. L., COCKAYNE, E. J., AND HEDETNIEMI, S. T. 1979. Linear algorithms on recursive ~representations of trees. J. Comput. Syst. Sci, 18, 76 85.Google Scholar
- ~MITCHELL, S. L., AND HEDETNIEMI, S. T. 1975. Edge domination in trees. In Proceedings of the ~8th Southeastern Conference on Combinatoncs, Graph Theory, and Computtng (Winnipeg, ~Canada).Google Scholar
- ~PAPADIMITR1OU, C. H., AND YANNAKAKIS, M. 1981. Worst-case ratios for planar graphs and the ~method of induction on faces. In Proceedings of tile 22nd Symposium on Foundatzons of ~Computer Sctence. IEEE, New York, pp. 358-363.Google Scholar
- ~TAKAMIZAWA, K., NISHIZEKI, T., AND SAITO, N. 1982. Linear-time computability of combmatoriai ~problems on series parallel graphs. J. ACM 29, 3, 623-641. Google Scholar
- ~YANNAKAKIS, M., AND GAVRIL, F. 1980. Edge dominating sets in graphs. SiAM J. on Appl. Math. ~38, 3, 364-372.Google Scholar
Index Terms
- Approximation algorithms for NP-complete problems on planar graphs
Recommendations
Total domination in planar graphs of diameter two
MacGillivary and Seyffarth [G. MacGillivray, K. Seyffarth, Domination numbers of planar graphs, J. Graph Theory 22 (1996) 213-229] proved that planar graphs of diameter two have domination number at most three. Goddard and Henning [W. Goddard, M.A. ...
Adapted list coloring of planar graphs
Given an edge coloring F of a graph G, a vertex coloring of G is adapted to F if no color appears at the same time on an edge and on its two endpoints. If for some integer k, a graph G is such that given any list assignment L to the vertices of G, with |...
Planar graphs without 4- and 5-cycles are acyclically 4-choosable
Let G=(V,E) be a graph. A proper vertex coloring of G is acyclic if G contains no bicolored cycle. Namely, every cycle of G must be colored with at least three colors. G is acyclically L-list colorable if for a given list assignment L={L(v):v@?V}, there ...
Comments