Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс:
http://elar.urfu.ru/handle/10995/24584
Название: | Мощностная задача Штейнера на ориентированном градуированном графе |
Другие названия: | The Cardinality Steiner Problem in a Directed Graded Graph |
Авторы: | Щербакова, В. А. Shcherbakova, V. A. |
Дата публикации: | 1998 |
Издатель: | Уральский государственный университет им. А. М. Горького |
Библиографическое описание: | Щербакова В. А. Мощностная задача Штейнера на ориентированном градуированном графе / В. А. Щербакова // Известия Уральского государственного университета. — 1998. — № 10. — (Сер. Математика и механика; Вып. 1). — С. 127-146. |
Аннотация: | Дается обзор результатов автора, посвященных задаче нахождения минимального по числу вершин поддерева, содержащего заданное множество помеченных вершин в заданном ориентированном градуированном графе. Показано, что такая задача NP-трудна. Обсуждаются различные точные и приближенные алгоритмы ее решения. Описаны два класса графов, в которых (при подходящем расположении помеченных вершин) исследуемая задача полиномиально разрешима. We survey the author’s result devoted to the problem of determining the minimal (in the vertex number) subtree containing a prescribed set of marked vertices of a directed graded graph. The problem is shown to be NP-hard. We discuss several exact and approximate algorithms for its solution and describe two classes of graphs in which the problem admits a solution in polynomial time (provided a suitable disposition of marked vertices). |
URI: | http://elar.urfu.ru/handle/10995/24584 |
Идентификатор РИНЦ: | https://elibrary.ru/item.asp?id=52264738 |
Источники: | Известия Уральского государственного университета. 1998. № 10 |
Располагается в коллекциях: | Известия Уральского государственного университета. Математика и Механика. Компьютерные науки |
Файлы этого ресурса:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
iurm-1998-10-09.pdf | 339,51 kB | Adobe PDF | Просмотреть/Открыть |
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.