5/28/2023 0 Comments Unit disk graph x bounded chi![]() ![]() Nieberg, T., Hurink, J.L.: A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs, Memorandum No. In: Hromkovič, J., Nagl, M., Westfechtel, B. Nieberg, T., Hurink, J.L., Kern, W.: A Robust PTAS for Maximum Weight Independent Sets in Unit Disk Graphs. Matsui, T.: Approximation Algorithms for Maximum Independent Set Problems and Fractional Coloring Problems on Unit Disk Graphs. Marathe, M.V., Breu, H., Hunt III, H.B., Ravi, S.S., Rosenkrantz, D.J.: Simple Heuristics for Unit Disk Graphs. Hunt III, D.B., Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs. Hochbaum, D.S., Maass, W.: Approximation Schemes for Covering and Packing Problems in Image Processing and VLSI. Springer, New York (1999)Įrlebach, T., Jansen, K., Seidel, E.: Polynomial-time Approximation Schemes for Geometric Graphs. SIAM, Philadelphia (2005)ĭowney, R.G., Fellows, M.R.: Parameterized Complexity. Math. 86(1–3), 165–177 (1990)ĭemaine, E.D., Hajiaghayi, M.: Bidimensionality: New Connections between FPT Algorithms and PTASs. Algorithms 46, 178–189 (2003)Ĭheng, X., Huang, X., Li, D., Wu, W., Du, D.-Z.: A Polynomial-Time Approximation Scheme for the Minimum Connected Dominating Set in Ad Hoc Wireless Networks. Acta Cybernetica 11(1–2), 1–22 (1993)Ĭhan, T.M.: Polynomial-time Approximation Schemes for Packing and Piercing Fat Objects. Soc. 58, 39 (1952)īodlaender, H.L.: A Tourist Guide through Treewidth. Springer, Berlin (1999)īaker, B.S.: Approximation Algorithms for NP-Complete Problems on Planar Graphs. Springer, Heidelberg (2002)Īusiello, G., Creszenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation - Combinatorial Optimization Problems and Their Approximability. Algorithms 52(2), 134–151 (2003)Īlber, J., Niedermeier, R.: Improved Tree Decomposition Based Algorithms for Domination-like Problems. Alber, J., Fiala, J.: Geometric Separation and Exact Solutions for the Parameterized Independent Set Problem on Disk Graphs.
0 Comments
Leave a Reply. |