1. Kyoto University Research Information Repository
  2. 400　数理解析研究所
  3. 1.講究録
  4. 2088 アルゴリズムと計算理論の基礎と応用
ダウンロード数: 34

    このアイテムの引用には次の識別子を使用してください: http://hdl.handle.net/2433/251597
このアイテムのファイル:
ファイル 記述 サイズフォーマット 
2088-07.pdf1.06 MBAdobe PDF見る/開く
完全メタデータレコード
DCフィールド値言語
dc.contributor.authorKurita, Kazuhiroen
dc.contributor.authorWasa, Kunihiroen
dc.contributor.authorArimura, Hirokien
dc.contributor.authorUno, Takeakien
dc.contributor.alternative栗田, 和宏ja
dc.contributor.alternative和佐, 州洋ja
dc.contributor.alternative有村, 博紀ja
dc.contributor.alternative宇野, 毅明ja
dc.contributor.transcriptionクリタ, カズヒロ-
dc.contributor.transcriptionワサ, クニヒロ-
dc.contributor.transcriptionアリムラ, ヒロキ-
dc.contributor.transcriptionウノ, タケアキ-
dc.date.accessioned2020-06-19T04:18:06Z-
dc.date.available2020-06-19T04:18:06Z-
dc.date.issued2018-08-
dc.identifier.issn1880-2818-
dc.identifier.urihttp://hdl.handle.net/2433/251597-
dc.description.abstractDominating 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.en
dc.format.mimetypeapplication/pdf-
dc.language.isoeng-
dc.publisher京都大学数理解析研究所ja
dc.publisher.alternativeResearch Institute for Mathematical Sciences, Kyoto Universityen
dc.subject.ndc410-
dc.titleEfficient Enumeration Algorithm for Dominating Sets in Bounded Degenerate Graphs (Foundations and Applications of Algorithms and Computation)en
dc.typedepartmental bulletin paper-
dc.type.niitypeDepartmental Bulletin Paper-
dc.identifier.ncidAN00061013-
dc.identifier.jtitle数理解析研究所講究録ja
dc.identifier.volume2088-
dc.identifier.spage44-
dc.identifier.epage52-
dc.textversionpublisher-
dc.sortkey07-
dc.addressGraduate School of Information Science and Technology, Hokkaido Universityen
dc.addressNational Institute of Informaticsen
dc.addressGraduate School of Information Science and Technology, Hokkaido Universityen
dc.addressNational Institute of Informaticsen
dc.address.alternative北海道大学大学院情報科学研究科ja
dc.address.alternative国立情報学研究所ja
dc.address.alternative北海道大学大学院情報科学研究科ja
dc.address.alternative国立情報学研究所ja
dcterms.accessRightsopen access-
dc.identifier.jtitle-alternativeRIMS Kokyurokuen
出現コレクション:2088 アルゴリズムと計算理論の基礎と応用

アイテムの簡略レコードを表示する

Export to RefWorks


出力フォーマット 


このリポジトリに保管されているアイテムはすべて著作権により保護されています。