Hierarchically specified unit disk graphs
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