Journal of the ACM Bibliography

Selected papers that cite this one

• Sanjeev Arora, Alan Frieze, and Haim Kaplan. A new rounding procedure for the assignment problem with applications to dense graph arrangement problems. In 37th Annual Symposium on Foundations of Computer Science, pages 21-30, Burlington, Vermont, 14-16 October 1996. IEEE.

• Sanjeev Arora, Michelangelo Grigni, David Karger, Philip Klein, and Andrzej Woloszyn. A polynomial-time approximation scheme for weighted planar graph TSP. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 33-41, San Francisco, California, 25-27 January 1998.

• Brenda S. Baker and Edward G. Coffman, Jr. Mutual exclusion scheduling. Theoretical Computer Science, 162(2):225-343, 20 August 1996.

• Reuven Bar-Yehuda, Dan Geiger, Joseph (Seffi) Naor, and Ron M. Roth. Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference. SIAM Journal on Computing, 27(4):942-959, August 1998.

• Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science, 209(1-2):1-45, 6 December 1998. Tutorial.

• Zhi-Zhong Chen. Efficient approximation schemes for maximization problems on K_{3,3}-free or K_5-free graphs. Journal of Algorithms, 26(1):166-187, January 1998.

• David Fernández-Baca and Giora Slutzki. Optimal parametric search on graphs of bounded tree-width. Journal of Algorithms, 22(2):212-240, February 1997.

• Harry B. Hunt III, Madhav V. Marathe, Venkatesh Radhakrishnan, S. S. Ravi, Daniel J. Rosenkrantz, and Richard E. Stearns. NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. Journal of Algorithms, 26(2):238-274, February 1998.

• Sanjeev Khanna and Rajeev Motwani. Towards a syntactic characterization of PTAS. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 329-337, Philadelphia, Pennsylvania, 22-24 May 1996.

• Madhav V. Marathe, Harry B. Hunt III, Richard E. Stearns, and Venkatesh Radhakrishnan. Approximation algorithms for PSPACE-hard hierarchically and periodically specified problems. SIAM Journal on Computing, 27(5):1237-1261, October 1998.

• M. V. Marathe and S. S. Ravi. On approximation algorithms for the minimum satisfiability problem. Information Processing Letters, 58(1):23-29, 8 April 1996.

• Dimitrios M. Thilikos and Hans L. Bodlaender. Fast partitioning l-apex graphs with applications to approximating maximum induced-subgraph problems. Information Processing Letters, 61(5):227-232, 14 March 1997.

Selected references

• R. Bar-Yehuda and S. Even. On approximating a vertex cover for planar graphs. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pages 303-309, San Francisco, California, 5-7 May 1982.

• John Hopcroft and Robert Tarjan. Efficient planarity testing. Journal of the ACM, 21(4):549-568, October 1974.

• Christos H. Papadimitriou and Mihalis Yannakakis. Worst-case ratios for planar graphs and the method of induction on faces (extended abstract). In 22nd Annual Symposium on Foundations of Computer Science, pages 358-363, Nashville, Tennessee, 28-30 October 1981. IEEE.

• K. Takamizawa, T. Nishizeki, and N. Saito. Linear-time computability of combinatorial problems on series-parallel graphs. Journal of the ACM, 29(3):623-641, July 1982.

Shortcuts: