オイラー有向グラフにおける2本の辺素なパスの存在判定
スポンサーリンク
概要
- 論文の詳細を見る
2組の点対{x_1,x_2},{y_1,y_2}を持つオイラー有向グラフ(G;{x_1,x_2},{y_1,y_2})は、辺素なx'x"-パス,y'y"-パスを持つとき実行可能と言う。ここで、x'x"=x_1x_2あるいはx'x"=x_2x_1(y'y"=y_1y_2あるいはy'y"=y_2y_1)であればよい。本報告では、極小な実行不可能な問題例は、必ず特別な平面グラフ表現を持つことを示す。この実行不可能問題例に対する特徴付けに基づけば、問題例の実行可能性をο(m+nlogn)時間で判定することができ、実行可能な問題例に対しては、実際に辺素なx'x"-パス,y'y"-パスをο(m(m+nlogn))時間で見出だすことができる。ここで、n,mはそれぞれ問題例の点数、辺数である。
- 社団法人電子情報通信学会の論文
- 1995-09-22
著者
関連論文
- タンク繰りにおける経路探索法
- 2-A-3 MAX-2-SATに対する分枝限定法の改良(離散最適化(3))
- 1-A-5 矩形パッキング問題に対する厳密解法(離散最適化(2))
- 動的交通流配分のネットワーク・モデル
- スケジューリングの理論
- 無向ネットワーク内の全ての最小カットを表すカクタス表現の構成について(グラフ理論(1))
- 部分定義論理関数のホーン拡張について
- オプションプライシングと凸計画問題の関係について(金融工学(3))
- 給油施設操業スケジューリング
- 1-D-8 紙管製造工程における1次元カッティングストック問題(離散アルゴリズム(3))
- ネットワークの辺連結度増加問題を解くアルゴリズムの計算機実験(グラフ理論(2))
- アルゴリズム研究会(研究会千夜一夜)
- 離散構造を紐解くグラフ連結度アルゴリズム(文献賞受賞招待講演)
- 1-F-2 時間依存距離付きネットワークにおける2地点間の最短路アルゴリズム(動的計画)
- 劣モジュラ, 正モジュラ集合関数の多重グラフによる増大法
- 辺連結度増加関数の計算法(ネットワーク(1))
- Augmenting a (k-1)-Vertex-Connected Multigraph to an l-Edge-Connected and k-Vertex-Connected Multigraph
- Optimally Augmenting to Make a Biconnected Graph Four-Edge and Three-Vertex Connected
- Augmenting edge-connectivity and vertex-connectivity simultaneously
- 辺連結度,点連結度を同時に最適増大させる問題
- 機械式立体駐車場入出庫スケジューリング
- 機械式立体駐車場出庫スケジューリング
- 無向ネットワークの最小カットを求める実用的高速アルゴリズム(グラフ・ネットワーク)
- A Tight Upper Bound on the Number of Small Cuts in Undirected Networks
- Vehicle Scheduling on a Tree to Minimize Maximum Lateness(スケジューリング(2))
- リリースタイムとハンドリングタイムを考慮した木状経路における搬送スケジューリング(スケジューリング)
- 最近のアルゴリズムから : OR若手から一言(OR : 21世紀に向けて)
- 正理論関数の部分データに基づく正決定木の構成について(組み合わせ最適化(3))
- メタ戦略とラグランジュ緩和(「スケジューリング技術の新たな展開特集号」)
- オイラー有向グラフにおける2本の辺素なパスの存在判定
- 最適化アルゴリズムの最近の動き
- 無向グラフにおけるk-辺分割問題の一般化について