Том 4, серия 2, номер 2, 1997 г., Стр. 10-22
УДК 519.854
П. В. Ефремов
Паросочетания в геометрических двудольных графах
Аннотация:
Вводятся понятия двудольного геометрического графа и геометрического паросочетания. Исследуются их связи с перестановками и графами перестановок, изучаются некоторые свойства геометрических графов и паросочетании в них. Рассматриваются различные задачи о паросочетаниях применительно к классу двудольных геометрических графов. Представлены эффективные алгоритмы решения этих задач. Доказывается корректность алгоритмов, обсуждаются некоторые аспекты их реализации.
Библиогр. 2.
Ефремов П. В. 1
1. Уральский государственный университет, мат.-мех. факультет,
пр. Ленина, 51, 620083 Екатеринбург, Россия
е-mail: epv@skazna.ural.ru
Статья поступила 11 марта 1997 г.
