ダウンロード数: 33
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
2088-07.pdf | 1.06 MB | Adobe PDF | 見る/開く |
タイトル: | Efficient Enumeration Algorithm for Dominating Sets in Bounded Degenerate Graphs (Foundations and Applications of Algorithms and Computation) |
著者: | Kurita, Kazuhiro Wasa, Kunihiro Arimura, Hiroki Uno, Takeaki |
著者名の別形: | 栗田, 和宏 和佐, 州洋 有村, 博紀 宇野, 毅明 |
発行日: | Aug-2018 |
出版者: | 京都大学数理解析研究所 |
誌名: | 数理解析研究所講究録 |
巻: | 2088 |
開始ページ: | 44 |
終了ページ: | 52 |
抄録: | Dominating sets are fundamental graph structures. However, enumeration of dominating sets has not received much attention. This study aims to propose an efficient enumeration algorithms for bounded degenerate graphs. The algorithm enumerates all the dominating sets for k-degenerate graphs in O(k) time per solution using O(n+m) space. Since planar graphs have a constant degeneracy, this algorithm can enumerate all such sets for planar graphs in constant time per solution. |
URI: | http://hdl.handle.net/2433/251597 |
出現コレクション: | 2088 アルゴリズムと計算理論の基礎と応用 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。