Augmenting Outerplanar Graphs to Meet Diameter Requirements

DOI Web Site Web Site 参考文献16件
  • Toshimasa Ishii
    DEPARTMENT OF INFORMATION AND MANAGEMENT SCIENCE OTARU UNIVERSITY OF COMMERCE OTARU 047‐8501 JAPAN

書誌事項

公開日
2013-01-24
資源種別
journal article
権利情報
  • http://onlinelibrary.wiley.com/termsAndConditions#vor
DOI
  • 10.1002/jgt.21719
公開者
Wiley

この論文をさがす

説明

<jats:title>Abstract</jats:title><jats:p>Given an undirected graph <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt21719-math-0001.png" xlink:title="urn:x-wiley:03649024:media:jgt21719:jgt21719-math-0001" /> and an integer <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt21719-math-0002.png" xlink:title="urn:x-wiley:03649024:media:jgt21719:jgt21719-math-0002" />, we consider the problem of augmenting <jats:italic>G</jats:italic> by a minimum set of new edges so that the diameter becomes at most <jats:italic>D</jats:italic>. It is known that no constant factor approximation algorithms to this problem with an arbitrary graph <jats:italic>G</jats:italic> can be obtained unless <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/jgt21719-math-0003.png" xlink:title="urn:x-wiley:03649024:media:jgt21719:jgt21719-math-0003" />, while the problem with only a few graph classes such as forests is approximable within a constant factor. In this article, we give the first constant factor approximation algorithm to the problem with an outerplanar graph <jats:italic>G</jats:italic>. We also show that if the target diameter <jats:italic>D</jats:italic> is even, then the case where <jats:italic>G</jats:italic> is a partial 2‐tree is also approximable within a constant.</jats:p>

収録刊行物

参考文献 (16)*注記

もっと見る

関連プロジェクト

もっと見る

詳細情報 詳細情報について

問題の指摘

ページトップへ