Hierarchical Chinese Postman Problem: slightest disorder makes it hard, disconnectedness is manageable - Доклады на конференциях | Sciact - Система учета научной деятельности ИМ СО РАН

Hierarchical Chinese Postman Problem: slightest disorder makes it hard, disconnectedness is manageable Доклады на конференциях

Язык

Английский

Тип доклада

Секционный

Url доклада

https://easychair.org/smart-program/MOTOR2021/2021-07-09.html#session:54121

Конференция

Mathematical optimization theory and operations research (MOTOR-2021)
05-10 июл. 2021 , Иркутск

Авторы

Афанасьев Всеволод Альбертович ² , Ван Беверн Рене Андреасович ² , Цидулко Оксана Юрьевна ¹

Организации

1	Институт математики им. С.Л. Соболева СО РАН
2	Новосибирский государственный университет

The Hierarchical Chinese Postman Problem is finding a shortest traversal of all edges of a graph respecting precedence constraints given by a partial order on classes of edges. We show that the special case with connected classes is NP-hard even on orders decomposable into a chain and an incomparable class. For the case with linearly ordered (possibly disconnected) classes, we get 5/3-approximations and fixed-parameter algorithms by transferring results from the Rural Postman Problem.

Афанасьев В.А. , Ван Беверн Р.А. , Tsidulko O.Y.
Hierarchical Chinese Postman Problem: slightest disorder makes it hard, disconnectedness is manageable
Mathematical optimization theory and operations research (MOTOR-2021) 05-10 Jul 2021