制約付き非交差静定グラフ列挙アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
本論では,平面上に一般の位置に与えられたn頂点からなる頂点集合Pに対して,P上に埋め込まれた,辺制約付き非交差静定グラフをすべて列挙するアルゴリズムについて述べる.静定グラフはラーマングラフとも呼ばれ,そのようなグラフ全体がマトロイドの基を作ることが知られている.一方,平面上に埋め込まれた無交差ラーマングラフ全体はマトロイドとはならない.本論文では,Avis and Fukudaによる逆探索法を用いて,無交差ラーマングラフの列挙が可能であることを示す.またあらかじめ用いる辺が一部指定されている場合も列挙が可能である.
- 社団法人情報処理学会の論文
- 2006-09-27
著者
-
谷川 眞一
京都大学工学研究科建築学専攻
-
加藤 直樹
Department of Architecture and Architectural Engineering, Kyoto University
-
谷川 眞一
Department of Architecture and Architectural Engineering, Kyoto University
-
AVIS David
School of Computer Science, McGill University
-
大崎 純
Department of Architecture and Architectural Engineering, Kyoto University
-
Streinu Ileana
Dept. of Comp. Science, Smith College
-
Streinu Ileana
Dept. Of Comp. Science Smith College
-
Avis David
School Of Computer Science Mcgill University
-
Avis David
School Of Computer Science And Gerad Mcgill University
関連論文
- 一様点要求を満たす根つき森分割と剛性理論への応用
- 不完全情報下での複数人の探索者によるグラフ探索問題 (コンピュテーション)
- 1-D-2 線的施設配置問題に関する研究(離散アルゴリズム(1))
- 11015 線的施設配置問題に関する基礎研究(数理・シミュレーション,情報システム技術)
- 分子構造に関する剛性予想の証明
- Enumerations of Non-crossing Geometric Graphs (Acceleration and Visualization of Computation for Enumeration Problems)
- DS-1-2 A Proof of the Molecular Conjecture
- 20389 自由度kのメカニズムの生成(形態創生・理論,構造I)
- DS-1-6 無交差幾何グラフ列挙アルゴリズム(DS-1. COMP-NHC学生シンポジウム,シンポジウムセッション)
- 20167 静定トラス列挙アルゴリズムを利用したコンプライアントメカニズムの生成(形態解析・形態創生,構造I)
- 11016 必要部材制約付き平面無交差静定構造列挙アルゴリズム(数理・シミュレーション,情報システム技術)
- 制約付き無交差全域木列挙アルゴリズム
- 124 メカニズム最適化のための平面無交差静定構造列挙アルゴリズム
- 123 静定トラス列挙アルゴリズムを利用した柔構造物の最適設計
- 制約付き非交差静定グラフ列挙アルゴリズム
- 11021 平面無交差静定構造列挙アルゴリズム(シミュレーション : 計画・構造, 情報システム技術)
- グリッドを用いた折れ線近似に関する研究
- 11014 必要部材種類数制約下における平面三角形分割手法に関する研究(図形処理・画像処理,情報システム技術)
- 異なる辺長種類数制約下における一様三角形メッシュ生成アルゴリズム
- 不完全情報下での複数人の探索者によるグラフ探索問題
- 20174 剛板ヒンジ構造の組合せ剛性(位相最適化,構造I)
- From Bell Inequalities to Tsirelson's Theorem
- A Quantum Protocol to Win the Graph Colouring Game on All Hadamard Graphs(Discrete Mathematics and Its Applications)
- DS-1-7 無交差ラーマンフレームワーク列挙アルゴリズム(DS-1.COMP-NHC学生シンポジウム,シンポジウム)
- Randomized Algorithms for Variance-Based $k$-Clustering
- 異なる辺長種類数制約下における一様三角形メッシュ生成アルゴリズム
- 異なる辺長種類数制約下における一様三角形メッシュ生成アルゴリズム
- A C Implementation of the Reverse Search Vertex Enumeration Algorithm(Computational Geometry and Discrete Geometry)
- 4.組合せ剛性理論に基づく構造物列挙(広がる列挙の技術-列挙による問題解決アプローチ-)
- 組合せ剛性理論に基づく構造物列挙