?
Schedule for one locomotive in a 3 station circuit
P. 1684–1687.
Лазарев А. А., Мусатова Е. Г., Хуснуллин Н. Ф.
Язык:
английский
Захаров В. А., Моделирование и анализ информационных систем 2020 Т. 27 № 3 С. 260–303
Конечные преобразователи, двухленточные автоматы и биавтоматы - взаимосвязанные вычислительные модели, ведущие свое происхождение от концепции конечного автомата. В вычислениях этих машин проявляется много общих черт, и удивительно, что методы анализа, разработанные для одной из указанных моделей, не находят подходящего применения в других моделях. Целью данной статьи является разработка единой методики построения быстрых алгоритмов проверки эквивалентности ...
Добавлено: 28 сентября 2020 г.
Zinder Y., Лазарев А. А., Мусатова Е. Г., Автоматика и телемеханика 2020 Т. 5 С. 91–104
Представлен полиномиальный алгоритм корректировки расписания движения поездов для случая, когда один из путей двухпутной железной дороги становится недоступным, оставшийся путь содержит разъезд, а все поезда делятся на две категории: приоритетные поезда, например пассажирские, и обычные поезда, к которым относятся большинство грузовых поездов. Представленный алгоритм минимизирует негативное влияние, оказываемое блокировкой пути, сначала для приоритетных поездов, а ...
Добавлено: 2 сентября 2020 г.
Малышев Д. С., Журнал Средневолжского математического общества 2020 Т. 22 № 1 С. 38–47
Задача о вершинной 3-раскраске для заданного графа состоит в том, чтобы проверить, возможно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Наследственный класс графов — множество обыкновенных графов, замкнутое относительно изоморфизма и удаления вершин. Любой такой класс может быть задан множеством своих запрещенных порожденных подграфов. Известен сложностной статус задачи о вершинной 3-раскраске ...
Добавлено: 26 марта 2020 г.
Aziz H., Мулен Э. Ж., Сандомирский Ф. А., / Series arXiv "Computer Science and Game Theory (cs.GT), arXiv:1909.00740". 2019.
Добавлено: 24 сентября 2019 г.
Сандомирский Ф. А., Segal-Halevi E., / Series arXiv "Computer Science and Game Theory (cs.GT), arXiv:1908.01669". 2019.
Добавлено: 24 сентября 2019 г.
Branzei S., Сандомирский Ф. А., / Series arxiv "Computer Science and Game Theory (cs.GT), arXiv:1907.01766". 2019.
Добавлено: 24 сентября 2019 г.
Захаров В. А., В кн.: Дискретные модели в теории управляющих систем: Х Международная конференция, Москва и Подмосковье, 23-25 мая 2018 г. : Труды.: МГУ, МАКС Пресс, 2018. С. 128–130.
Показано, каким образом задача проверки эквивалентности двухленточных детерминированных автоматов может быть сведена к задаче проверки эквивалентности слабо недетерминированных конечных автоматов-преобразователей, работающих над полугруппой префиксных регулярных языков с операцией конкатенации. ...
Добавлено: 14 июня 2018 г.
Zinder Y., Лазарев А. А., Musatova E. G. и др., Automation and Remote Control 2018 Vol. Vol. 79 No. 3 P. 506–523
Добавлено: 30 мая 2018 г.
А.А.Лазарев, Зиндер Я., Мусатова Е. Г. и др., Автоматика и телемеханика 2018 № 3 С. 144–166
Рассматривается построение расписания двухстороннего движения поездов между двумя станциями, соединенными однопутной железной дорогой с разъездом. Показано, что если для каждой станции известен или может быть найден порядок отправления поездов, то для различных целевых функций за полиномиальное от количества поездов время может быть построено оптимальное расписание методом динамического программирования. На основе данного результата предложен полиномиальный алгоритм ...
Добавлено: 30 мая 2018 г.
Канович М. И., Кузнецов С. Л., Morrill G. и др., , in: Second International Conference on Formal Structures for Computation and Deduction, FSCD 2017Vol. 84: 2nd International Conference on Formal Structures for Computation and Deduction (FSCD 2017).: [б.и.], 2017. P. 22:1–22:17.
Добавлено: 15 сентября 2017 г.
Протасов В. Ю., Войнов А. С., Linear Algebra and its Applications 2017 No. 513 P. 376–408
Multiplicative matrix semigroups with constant spectral radius (c.s.r.) are studied and applied to several problems of algebra, combinatorics, functional equations, and dynamical systems. We show that all such semigroups are characterized by means of irreducible ones. Each irreducible c.s.r. semigroup defines walks on Euclidean sphere, all its nonsingular elements are similar (in the same basis) ...
Добавлено: 11 марта 2017 г.
Протасов В. Ю., SIAM Journal on Matrix Analysis and Applications 2013 Vol. 34 No. 3 P. 1174–1188
We develop a new approach for characterizing $k$-primitive matrix families. Such families generalize the notion of a primitive matrix. They have been intensively studied in the recent literature due to applications to Markov chains, linear dynamical systems, and graph theory. We prove, under some mild assumptions, that a set of $k$ nonnegative matrices is either ...
Добавлено: 19 февраля 2016 г.
Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2014 Vol. 8 No. 2 P. 245–255
Добавлено: 8 мая 2014 г.
Малышев Д. С., Вестник Нижегородского университета им. Н.И. Лобачевского 2014 Т. 3 № 1 С. 288–290
В работе показывается, что задача о раскраске полиномиально разрешима в классе графов Free({claw,bull}). ...
Добавлено: 7 апреля 2014 г.
Малышев Д. С., Дискретный анализ и исследование операций 2013 Т. 20 № 6 С. 59–76
Задача о реберном списковом ранжировании является обобщением классической задачи о раскраске ребер графа и математической моделью протекания ряда параллельных процессов. В настоящей работе исследуется вычислительная сложность данной задачи для замкнутых относительно изоморфизма и удаления вершин множеств графов (наследственных классов). Описываются все конечно определенные и минорно замкнутые случаи, для которых эта задача полиномиально разрешима. Выявляется вся ...
Добавлено: 23 октября 2013 г.
Малышев Д. С., Дискретный анализ и исследование операций 2012 Т. 19 № 3 С. 58–64
В работе предлагается алгоритм, который определяет число независимости n-вершинного графа из класса Free({P5,C5, Kp}) за время O(np+O(1)). ...
Добавлено: 6 июня 2012 г.