09:40 〜 10:00
[2E1-OS-13a-03] 大きな極大マッチングの多項式遅延列挙
キーワード：列挙、極大マッチング、サイズ制約
私たちは与えられた閾値t より大きな要素数を持つ極大マッチングの列挙に対して，2つの多項式遅延列挙アルゴリズムを与える．まず1つ目のアルゴリズムはそのような全てのマッチングをO(m2)遅延で列挙する．ここで，mはグラフ中の辺の本数である．この結果は既存の極大マッチング列挙に対して，要素数制約を追加した結果である．2つ目のアルゴリズムは全ての極大マッチングを要素数が非増加の順序で列挙するアルゴリズムであり，これも多項式遅延で動作する．
講演PDFパスワード認証
論文PDFの閲覧にはログインが必要です。参加登録者の方は「参加者用ログイン」画面からログインしてください。あるいは論文PDF閲覧用のパスワードを以下にご入力ください。