Точные алгоритмы построения доминирующего множества: различия между версиями

Простые алгоритмы ветвления и редукции в наихудшем случае, подобные алгоритмам нахождения минимального доминирующего множества или минимального покрытия множества, также пока неизвестны. В случае алгоритма нахождения минимального доминирующего множества с использованием полиномиального объема памяти разрыв между верхней границей O(20.610n) и нижней границей Q(2nl3) слишком велик. Подобная же ситуация наблюдается и для других алгоритмов ветвления и редукции. Следовательно, существует значительная потребность в новых и более мощных инструментах анализа алгоритмов ветвления и редукции в наихудшем случае.

   

1. Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccalema, A., Protasi, M.: Complexity and Approximation. Springer, Berlin (1999)

2. Byskov, J.M.: Exact algorithms for graph colouring and exact satisfiability. Ph.D. thesis, University of Aarhus, Denmark (2004)

3. Downey,  R.G.,  Fellows,  M.R.:  Parameterized  complexity. Springer, New York (1999)

4. Eppstein, D.: Quasiconvex analysis of backtracking algorithms. I n: Proceed i ng s of SODA 2004, pp. 781 -790

5. Fomin, F.V., Grandoni, F., Kratsch, D.: Measure and conquer: Domination - A case study. In: Proceedings of ICALP 2005. LNCS, vol. 3380, pp. 192-203. Springer, Berlin (2005)

6. Fomin,  F.V., Grandoni,  F., Kratsch, D.:  Measure and  Conquer: A simple O(20.288n) Independent Set Algorithm. In: Proceedings of SODA 2006, pp. 18-25

7. Fomin, F.V., Kratsch, D., Woeginger, G.J.: Exact (exponential) algorithms for the dominating set problem. In: Proceedings of WG 2004. LNCS, vol. 3353, pp. 245-256. Springer, Berlin (2004)

8. Grandoni, F.: Exact Algorithms for Hard Graph Problems. Ph. D. thesis, Universita di Roma "Tor Vergata", Roma, Italy (2004)

9. Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of domination in graphs. Marcel Dekker, New York (1998)

10. Kratsch, D.: Algorithms. In: Haynes, T., Hedetniemi, S., Slater, P. (eds.) Domination in Graphs: Advanced Topics, pp. 191-231. Marcel Dekker, New York (1998)

11. Randerath, B., Schiermeyer, I.: Exact algorithms for MINIMUM DOMINATING SET. Technical Report, zaik-469, Zentrum fur Angewandte Informatik Koln (2004)

12. Woeginger, G.J.: Exact algorithms for NP-hard problems: A survey. In: Combinatorial Optimization - Eureka, You Shrink.LNCS, vol. 2570, pp. 185-207. Springer, Berlin (2003)