4551
правка
Редукция данных для доминирования в графах: различия между версиями
Материал из WEGA
Редукция данных для доминирования в графах (посмотреть исходный код)
Версия от 01:37, 25 марта 2013
, 25 марта 2013→Литература
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 60: | Строка 60: | ||
== Литература == | == Литература == | ||
1. Alber, J., Betzler, N., Niedermeier, R.: Experiments on data reduction for optimal domination in networks. Ann. Oper. Res. 146(1), 105–117 (2006) | 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) | 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) | 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) | 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) | 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) | 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) | 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) | 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) | 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) | 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) | 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) | 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) | 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) | 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) | 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) | 16. Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, New York (2006) | ||
