Hierarchically specified unit disk graphs

Theoretical Computer Science - Tập 174 - Trang 23-65 - 1997
Madhav V. Marathe1, Venkatesh Radhakrishnan2, Harry B. Hunt3, S.S. Ravi3
1P.O. Box 1663, MS K990, Los Alamos National Laboratory, Los Alamos, NM 87545, USA
2Mailstop 47LA, Hewlett-Packard Company, 19447 Pruneridge Avenue, Cupertino, CA 95014-9913, USA
3Department of Computer Science, University at Albany — SUNY, Albany, NY 12222, USA

Tài liệu tham khảo

Arora, 1992, Proof verification and hardness of approximation problems, 14 Bentley, 1984, The complexity of manipulating hierarchically defined set of rectangles, Vol. 1, 127 Clark, 1990, Unit disk graphs, Discrete Math., 86, 165, 10.1016/0012-365X(90)90358-O Cohen, 1989, Strongly polynomial-time and NC algorithms for detecting cycles in dynamic graphs, 523 Condon, 1993, Probabilistically checkable debate systems and approximation algorithms for PSPACE-Hard Functions, 305 Condon, 1994, Random debators and the hardness of approximating stochastic functions for PSPACE-hard functions, 280 Fowler, 1981, Optimal packing and covering in the plane are NP-complete, Inform. Process. Lett., 12, 133, 10.1016/0020-0190(81)90111-3 Galperin, 1982, Succinct representation of graphs, 10.1016/S0019-9958(83)80004-7 Garey, 1979 Ghezzi, 1991 Halldórsson, 1995, Approximating discrete collections via local improvements, 160 Hochbaum, 1985, Approximation schemes for covering and packing problems in image processing and VLSI, J. ACM, 32, 130, 10.1145/2455.214106 Höfting, 1992, Processing of hierarchically defined graphs and graph families, Vol. 594, 44 Höfting, 1992, Minimum cost paths in periodic graphs, 10.1137/S0097539792234378 Höfting, 1993, 493 Hunt, 1994, A unified approach to approximation schemes for NP- and PSPACE-hard problems for geometric graphs, 424 Lengauer, 1986, Exploiting hierarchy in VLSI design, Vol. 227, 180 Lengauer, 1987, Efficient algorithms for finding minimum spanning forests of hierarchically defined graphs, J. Algorithms, 8, 260, 10.1016/0196-6774(87)90042-3 Lengauer, 1989, Hierarchical planarity testing, J. ACM, 36, 474, 10.1145/65950.65952 Lengauer, 1992, The correlation between the complexities of non-hierarchical and hierarchical versions of graph problems, J. Comput. System Sci., 44, 63, 10.1016/0022-0000(92)90004-3 Lengauer, 1988, Efficient solutions for connectivity problems for hierarchically defined graphs, SIAM J. Comput., 17, 1063, 10.1137/0217068 Lengauer, 1987, Efficient solutions for hierarchical systems of linear equations, Computing, 39, 111, 10.1007/BF02310101 Lund, 1993, On the hardness of approximating minimization problems, 286 Lund, 1994, J. ACM, 41, 960, 10.1145/185675.306789 Marathe, 1995, Simple heuristics for unit disk graphs, Networks, 25, 59, 10.1002/net.3230250205 Marathe, 1993, The complexity of approximating PSPACE-complete problems for hierarchical specifications, 76 Marathe, 1994, Nordic J. Comput., 1, 275 Marathe, 1994, Approximation schemes for PSPACE-complete problems for succinct graphs, 468 Marathe, 1995, Complexity of hierarchically and 1-dimensional periodically specified problems Marathe, 1995 McClain, 1992 Mead, 1980 Meggido, 1984, On the complexity of some common geometric location problems, SIAM J. Comput., 13, 182, 10.1137/0213014 Orlin, 1984, Some problems on dynamic/periodic graphs, 273 Ullman, 1988, Vol. 1 Wagner, 1984, The complexity of problems concerning graphs with regularities, Vol. 176, 544 M. Williams, Efficient processing of hierarchical graphs, Technical Report 90-06, Dept. Computer Science, Iowa Sate University. (Parts of the report appeared in WADS'89 and SWAT'90 co-authored with D. Fernandez-Baca.) Wang, 1988, A study on geometric location problems, Inform. Process. Lett., 28, 281, 10.1016/0020-0190(88)90174-3