4551
правка
Двумерность: различия между версиями
Материал из WEGA
→Открытые вопросы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 57: | Строка 57: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
В теории двумерности и родственных направлениях остаются нерешенными несколько комбинаторных и алгоритмических задач. | |||
Можно ли обобщить теорему 2 о соотношении древесной ширины и решетки в свободных от H-миноров графах на произвольные графы с полиномиальным соотношением между древесной шириной и наибольшим минором-решеткой? (Наилучшее известное соотношение является экспоненциальным). Подобные полиномиальные обобщенные подходы были получены для случаев «графов-карт» и «графов высоких степеней» [9]. Удачные границы соотношения древесной ширины и решетки находят применение в минорно-двумерных задачах. | |||
Можно ли обобщить алгоритмические результаты (теоремы 3 и 4) для решения задач о двумерности со сжатием, не ограничивающихся графами, свободными от апексных миноров? Известно, что лежащая в основе этих результатов теорема 1 не допускает обобщения [1]. Тем не менее, теорему 3 удалось обобщить для одной конкретной задачи о двумерности со сжатием – доминирующего множества [ ]. | |||
Можно ли обобщить схемы аппроксимации с полиномиальным временем выполнения из теоремы 4 до алгоритмических задач более общего вида, не сопоставленных напрямую с двумерными параметрами? Один пример семейства подобных задач общего вида появляется при назначении вершинам и/или ребрам весов и необходимости вычислить, например, доминирующее множество с минимальным весом. Еще один пример такой задачи возникает при накладывании ограничений (например, на покрытие или доминирование) только на подмножества вершин и/или ребер. В качестве примеров таких задач можно привести алгоритмы построение дерева Штейнера и разрывающего множества вершин. | |||
Другие открытые вопросы и подробное изложение перечисленных можно найти в [4]. | |||
== См. также == | |||
* ''[[Схемы аппроксимации для задач с планарными графами]] | |||
* ''[[Путевая ширина графа]] | |||
* ''[[Древесная ширина графа]] | |||
== Литература == | |||
1. Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Bidimensional parameters and local treewidth. SIAM J. Discret. Math. 18(3), 501-511 (2004) | |||
2. Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Fixed-parameter algorithms for (k,r)-center in planar graphs and map graphs. ACM Trans. Algorithms 1(1), 33^7 (2005) | |||
3. Demaine, E.D., Fomin, F.V., Hajiaghayi, M.,Thilikos, D.M.: Subexponential parametrized algorithms on graphs of bounded genus and H-minor-free graphs. J. ACM 52(6), 866-893 (2005) | |||
4. Demaine, E.D., Hajiaghayi, M.:The bidimensionality theory and its algorithmic applications. Comput. J. To appear | |||
5. Demaine, E.D., Hajiaghayi, M.: Diameter and treewidth in minor-closed graph families, revisited. Algorithmica 40(3),211-215(2004) | |||
6. Demaine, E.D., Hajiaghayi, M.: Equivalence of local treewidth and linear local treewidth and its algorithmic applications. In: Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA'04), January 2004, pp. 833-842 (2004) | |||
7. Demaine, E.D., Hajiaghayi, M.: Bidimensionality: New connections between FPT algorithms and PTASs. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 590-601. Vancouver, January (2005) | |||
8. Demaine, E.D., Hajiaghayi, M.: Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 682-689. Vancouver, January (2005) | |||
9. Demaine, E.D., Hajiaghayi, M., Kawarabayashi, K.: Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction. In: Proceedings of the 17th Annual International Symposium on Algorithms and Computation, Calcutta, India, December 2006. Lecture Notes in Computer Science, vol.4288, pp. 3-15(2006) | |||
10. Demaine, E.D., Hajiaghayi, M., Nishimura, N., Ragde, P., Thilikos, D.M.: Approximation algorithms for classes of graphs excluding single-crossing graphs as minors. J. Comput. Syst. Sci. 69(2),166-195(2004) | |||
11. Demaine, E.D., Hajiaghayi, M., Thilikos, D.M.: Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors. Algorithmica41(4),245-267(2005) | |||
12. Demaine, E.D., Hajiaghayi, M., Thilikos, D.M.: The bidimensional theory of bounded-genus graphs. SIAM J. Discret. Math. 20(2), 357-371 (2006) | |||
