ГлавнаяАрхивО погрешности полиномиального вычисления оптимальной раскраски графа в синхронизируемый автомат

О погрешности полиномиального вычисления оптимальной раскраски графа в синхронизируемый автомат | Прикладная дискретная математика. 2011. № 2(12).

Сильносвязный орграф называется допустимым, если исходящие степени всех вершин в нём одинаковы и длины циклов взаимно просты в совокупности. Раскраской допустимого графа G назовем произвольный автомат A, граф которого совпадает с G. Слово называется синхронизирующим автомат A, если оно переводит его в одно и то же состояние вне зависимости от исходного состояния автомата A. Оптимальная раскраска допустимого графа -это раскраска с кратчайшим синхронизирующим словом среди всех синхронизирующих раскрасок. Длину соответствующего синхронизирующего слова назовем значением оптимальной раскраски. Доказано, что любой приближенный полиномиальный алгоритм для вычисления оптимальной раскраски или ее значения имеет относительную погрешность не меньше 2 в случае трехбуквенного алфавита при предположении P = NP. Также показано, как результат можно перенести на случай двухбуквенного алфавита.
  • Title О погрешности полиномиального вычисления оптимальной раскраски графа в синхронизируемый автомат
  • Headline О погрешности полиномиального вычисления оптимальной раскраски графа в синхронизируемый автомат
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 2(12)
  • Date:
  • DOI
Ключевые слова
optimal coloring, synchronizing automata, road coloring problem, синхронизируемые автоматы, кратчайшее синхронизирующее слово, поиск оптимальной раскраски, проблема раскраски дорог
Авторы
Ссылки
Гэри M., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
Berlinkov M. Approximating the Minimum Length of Synchronizing Words is Hard // LNCS. 2010. V. 6072. P. 37-47.
Beal M. and Perrin D. A quadratic algorithm for road coloring // arXiv:0803.0726. 2008.
Eppstein D. Reset sequences for monotonic automata // SIAM J. Comput. 1990. V. 19. P. 500-510.
Adler R. L. and Weiss B. Similarity of automorphisms of the torus // Mem. Amer. Math. Soc. 1970. V. 98. P. 1-43.
Volkov M. Synchronizing Automata and the Cerny conjecture // LNCS. 2008. V. 5196. P. 11-27.
Cerny J. Poznamka k homogennym eksperimentom s konecnymi automatami // Matematickofyzikalny Casopis Slovensk. Akad. Vied (in Slovak). 1964. V. 14. No.3. P.208-216.
Adler R. L., Weiss B., and Goodwyn L. W. Equivalents of topological Markov shifts // Isr. J. Math. 1977. No. 27. P. 49-63.
Trahtman A. N. The Road Coloring Problem // arxiv:0709.0099. 2007.
О погрешности полиномиального вычисления оптимальной раскраски графа в синхронизируемый автомат | Прикладная дискретная математика. 2011. № 2(12).
О погрешности полиномиального вычисления оптимальной раскраски графа в синхронизируемый автомат | Прикладная дискретная математика. 2011. № 2(12).
Полнотекстовая версия