Редукция данных для доминирования в графах: различия между версиями

== Литература ==

1. Alber, J., Betzler, N., Niedermeier, R.: Experiments on data reduction for optimal domination in networks. Ann. Oper. Res. 146(1), 105–117 (2006)

2. Alber, J., Bodlaender, H.L., Fernau, H., Kloks, T., Niedermeier, R.: Fixed parameter algorithms for Dominating Set and related problems on planar graphs. Algorithmica 33(4), 461–493 (2002)

3. Alber, J., Dorn, B., Niedermeier, R.: A general data reduction scheme for domination in graphs. In: Proc. 32nd SOFSEM. LNCS, vol. 3831, pp. 137-147. Springer, Berlin (2006)

4. Alber, J., Fan, H., Fellows, M.R., Fernau, H., Niedermeier, R., Rosamond, F., Stege, U.: A refined search tree technique for Dominating Set on planar graphs. J. Comput. Syst. Sci. 71(4), 385^05 (2005)

5. Alber, J., Fellows, M.R., Niedermeier, R.: Polynomial time data reduction for Dominating Set. J. ACM 51 (3), 363-384 (2004)

6. Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41(1), 153-180 (1994)

7. Chen, J., Fernau, H., Kanj, I.A., Xia, G.: Parametric duality and kernelization: lower bounds and upper bounds on kernel size. SIAM J. Comput. 37(4), 1077-1106 (2007)

8. Downey,  R.G.,  Fellows,  M.R.:  Parameterized  Complexity. Springer, New York (1999)

9. Feige, U.: A threshold of lnn for approximating set cover. J. ACM 45(4), 634-652 (1998)

10. Fomin, F.V., Thilikos, D.M.: Fast parameterized algorithms for graphs on surfaces: Linear kernel and exponential speed-up. In: Proc. 31st ICALP. LNCS, vol. 3142, pp. 581-592. Springer, Berlin (2004)

11. Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. ACM SIGACT News 38(1), 31-45 (2007)

12. Guo, J., Niedermeier,  R.: Linear  problem  kernels  for  NP-hard problems on planar graphs. In: Proc. 34th ICALP. LNCS, vol. 4596, pp. 375-386. Springer, Berlin (2007)

13. Guo,  J.,  Niedermeier,  R.,  Wernicke,  S.:  Fixed-parameter tractability results for full-degree spanning tree and its dual. In: Proc. 2nd IWPEC. LNCS, vol. 4196, pp. 203-214. Springer, Berlin (2006)

14. Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Domination  in Graphs: Advanced Topics. Pure and Applied Mathematics, vol. 209. Marcel Dekker, New York(1998)

15. Haynes, T.W.,  Hedetniemi,  S.T.,  Slater,  P.J.:  Fundamentals of Domination in Graphs. Pure and Applied Mathematics, vol. 208. Marcel Dekker, New York(1998)

16. Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, New York (2006)