対称二部グラフのマッチング構造
スポンサーリンク
概要
- 論文の詳細を見る
対称二部グラフとは,二つの頂点集合を分ける軸で線対称性を持つ二部グラフである.本発表では,対称な二部グラフのマッチング構造を調べることを目的とする.まず対称な二部グラフに対しDulmage-Mendelsohn分解を行なうと,得られた成分(マッチング被覆グラフ)は対称性を有することが分かる.マッチング被覆二部グラフは,耳分解により,ある辺に長さ奇数のパスを繰り返し付け加えることで構成できる.本研究では,マッチング被覆二部グラフが対称ならば高々2本のパスを付け加えることで対称性を保持したまま耳分解できることを示す.さらに,対称二部グラフの組合せ的行列理論への応用として,Polyaの問題を一般化した問題を提案し,その問題が多項式可解であることを述べる.
- 2008-09-05
著者
関連論文
- 2-D-2 コーダル構造を持つ半正定値対称行列に対する極大クリーク行列分解の直接的な証明(離散・組合せ最適化(5))
- 対称二部グラフのマッチング構造
- 離散凸最適化ソルバとデモンストレーションソフトウェアの公開
- 数理計画と組合せ的行列理論(最先端を目指す若手研究者達)
- 数理計画法における符号可解性(研究会推薦博士論文速報)
- 平成21年春季研究発表会ルポ(情報の窓)
- 2-C-3 線形相補性問題の符号可解性(グラフ・ネットワーク)
- 1-B-6 線形計画問題の符号可解性(組合せ最適化(1))
- 符号対称行列のSylvester指数(組合せ最適化(6))
- 線形相補性問題の符号可解性
- 1-D-5 デルタマトロイド制約付きマッチング(離散最適化(1))
- 1-C-10 疎な線形相補性問題に対する組合せ的アルゴリズム(離散最適化(1))
- 2-F-2 二部グラフ上の最適予算配分問題に対する高速アルゴリズム(離散最適化(4))
- 2-A-11 ロバスト独立システム(離散最適化(3))