Пусть G будет ненаправленным графом из n узлов, и пусть T будет подмножеством узлов V (G), называемых терминалами . Сохранитель расстояния (G, T) - это граф H, удовлетворяющий свойству
для всех узлов u, v в T. (Обратите внимание, что H НЕ обязательно является подграфом G.)
Например, пусть G - следующий граф (a), а T - узлы на внешней грани. Тогда граф (b) является сохранителем расстояния (G, T).
Известно, что сохранитель расстояния с различными параметрами существует. Я особенно заинтересован в одном со следующими свойствами:
- G плоская и невзвешенная (то есть все ребра G имеют вес один),
- T имеет размер и
- H имеет размер (количество узлов и ребер) . (Было бы хорошо, если бы у нас было .)
Существует ли такой сохранитель расстояния?
Если вы не можете встретить вышеупомянутые свойства, приветствуются любые виды релаксации.
Ссылки:
- Разреженные источники и парные сохранители расстояния , Дон Копперсмит и Майкл Элкин, СИДМА, 2006.
- Хранители редких расстояний и аддитивные гаечные ключи, Бела Боллобас, Дон Копперсмит и Майкл Элкин, СИДМА, 2005.
- Гаечные ключи и эмуляторы с ошибками сублинейного расстояния , Миккель Торуп и Ури Цвик, SODA, 2006.
- Нижние границы для аддитивных ключей, эмуляторов и многого другого, Дэвид П. Вудрафф, FOCS, 2006.
Сохранитель расстояния также известен как эмулятор ; многие связанные работы можно найти в Интернете, выполнив поиск по термину « гаечный ключ» , который требует, чтобы H был подграфом G. Но в моих приложениях мы можем использовать и другие графики, если H сохраняет расстояния между T в G.
источник
Ответы:
Спустя много лет, похоже, OP наконец-то ответил на свой вопрос: почти -оптимальный эмулятор расстояний для плоских графиков Сянь-Чжи Чанга, Павла Гавриховского, Шая Мозеса и Орен Вейманн только что был размещен на arxiv.
(На менее формальной ноте я нахожу этот результат действительно удивительным. Поздравляю!)
источник
Вы можете посмотреть на плоский гаечный ключ Кляйна, который сохраняет расстояния до 1 + эпсилон-фактор.
Гаечный ключ подмножества для плоских графов с приложением к подмножеству TSP http://doi.acm.org/10.1145/1132516.1132620
источник