?
Schedule for one locomotive in a 3 station circuit
P. 1684–1687.
Lazarev A. A., Мусатова Е. Г., Хуснуллин Н. Ф.
In this research it was considered the particular case of a railway problem, specifically, the construction of orders delivery schedule for one locomotive plying among three railway station. In this paper it was suggested a polynomial algorithm and were shown the results of a computing experiment.
Zakharov V., Моделирование и анализ информационных систем 2020 Т. 27 № 3 С. 260–303
Finite transducers, two-tape automata, and biautomata are related computational models descended from the concept of Finite State Automaton. In these models an automaton controls two heads that read or write symbols on the tapes in one-way mode. The computations of these three types of automata show many common features, and it is surprising that the ...
Added: September 28, 2020
Zinder Y., Lazarev A. A., Musatova E. G., Автоматика и телемеханика 2020 Т. 5 С. 91–104
Представлен полиномиальный алгоритм корректировки расписания движения поездов для случая, когда один из путей двухпутной железной дороги становится недоступным, оставшийся путь содержит разъезд, а все поезда делятся на две категории: приоритетные поезда, например пассажирские, и обычные поезда, к которым относятся большинство грузовых поездов. Представленный алгоритм минимизирует негативное влияние, оказываемое блокировкой пути, сначала для приоритетных поездов, а ...
Added: September 2, 2020
Malyshev D., Журнал Средневолжского математического общества 2020 Т. 22 № 1 С. 38–47
Задача о вершинной 3-раскраске для заданного графа состоит в том, чтобы проверить, возможно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Наследственный класс графов — множество обыкновенных графов, замкнутое относительно изоморфизма и удаления вершин. Любой такой класс может быть задан множеством своих запрещенных порожденных подграфов. Известен сложностной статус задачи о вершинной 3-раскраске ...
Added: March 26, 2020
Aziz H., Moulin H., Sandomirskiy F., / Series arXiv "Computer Science and Game Theory (cs.GT), arXiv:1909.00740". 2019.
We consider fair allocation of indivisible items under additive utilities. When the utilities can be negative, the existence and complexity of an allocation that satisfies Pareto optimality and proportionality up to one item (PROP1) is an open problem. We show that there exists a strongly polynomial-time algorithm that always computes an allocation satisfying Pareto optimality ...
Added: September 24, 2019
Sandomirskiy F., Segal-Halevi E., / Series arXiv "Computer Science and Game Theory (cs.GT), arXiv:1908.01669". 2019.
A set of objects, some goods and some bads, is to be divided fairly among agents with different tastes, modeled by additive utility-functions. If the objects cannot be shared, so that each of them must be entirely allocated to a single agent, then fair division may not exist. What is the smallest number of objects ...
Added: September 24, 2019
Branzei S., Sandomirskiy F., / Series arxiv "Computer Science and Game Theory (cs.GT), arXiv:1907.01766". 2019.
We study the problem of allocating divisible bads (chores) among multiple agents with additive utilities, when money transfers are not allowed. The competitive rule is known to be the best mechanism for goods with additive utilities and was recently extended to chores by Bogomolnaia et al (2017). For both goods and chores, the rule produces ...
Added: September 24, 2019
Zakharov V., В кн.: Дискретные модели в теории управляющих систем: Х Международная конференция, Москва и Подмосковье, 23-25 мая 2018 г. : Труды.: МГУ, МАКС Пресс, 2018. С. 128–130.
It is shown how the verification of the equivalence of two-tape deterministic automata can be reduced to the problem of checking the equivalence of weakly nondeterministic finite automata-transformers working on the semigroup of prefix regular languages with the concatenation operation. ...
Added: June 14, 2018
Zinder Y., Lazarev A. A., Musatova E. G. et al., Automation and Remote Control 2018 Vol. Vol. 79 No. 3 P. 506–523
The paper is concerned with scheduling the two-way traffic between two stations connected by a single-track railway with a siding. It is shown that if, for each station, the order in which trains leave this station is known or can be found, then for various objective functions an optimal schedule can be constructed in polynomial ...
Added: May 30, 2018
А.А.Лазарев, Зиндер Я., Мусатова Е. Г. et al., Автоматика и телемеханика 2018 № 3 С. 144–166
The paper is concerned with scheduling the two-way traffic between two stations connected by a single-track railway with a siding. It is shown that if, for each station, the order in which trains leave this station is known or can be found, then for various objective functions an optimal schedule can be constructed in polynomial ...
Added: May 30, 2018
Kanovich M., Kuznetsov S., Morrill G. et al., , 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.
Lambek calculus is a logical foundation of categorial grammar, a linguistic paradigm of grammar as logic and parsing as deduction. Pentus (2010) gave a polynomial-time algorithm for determining provability of bounded depth formulas in L* , the Lambek calculus with empty antecedents allowed. Pentus’ algorithm is based on tabularisation of proof nets. Lambek calculus with ...
Added: September 15, 2017
Protasov V., Voinov A. S., 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) ...
Added: March 11, 2017
Protasov V., 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 ...
Added: February 19, 2016
Malyshev D., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2014 Vol. 8 No. 2 P. 245–255
The edge list-ranking problem is a generalization of the classical edge coloring problem, and it is a mathematical model for some parallel processes. The computational complexity of this problem is under study for graph sets closed under isomorphism and deletion of vertices (hereditary classes). Allfinitely defined and minor-closed cases are described for which the problem ...
Added: May 8, 2014
Malyshev D., Вестник Нижегородского университета им. Н.И. Лобачевского 2014 Т. 3 № 1 С. 288–290
В работе показывается, что задача о раскраске полиномиально разрешима в классе графов Free({claw,bull}). ...
Added: April 7, 2014
Malyshev D., Дискретный анализ и исследование операций 2013 Т. 20 № 6 С. 59–76
Задача о реберном списковом ранжировании является обобщением классической задачи о раскраске ребер графа и математической моделью протекания ряда параллельных процессов. В настоящей работе исследуется вычислительная сложность данной задачи для замкнутых относительно изоморфизма и удаления вершин множеств графов (наследственных классов). Описываются все конечно определенные и минорно замкнутые случаи, для которых эта задача полиномиально разрешима. Выявляется вся ...
Added: October 23, 2013
Malyshev D., Дискретный анализ и исследование операций 2012 Т. 19 № 3 С. 58–64
An algorithm is implemented in the article for finding the independence number of a n-vertex graph from the class Free({P5,C5, Kp}) in time O(np+O(1)). ...
Added: June 6, 2012