| アイテムタイプ |
Article |
| ID |
|
| プレビュー |
| 画像 |
|
| キャプション |
|
|
| 本文 |
KO50001004-00290004-0041.pdf
| Type |
:application/pdf |
Download
|
| Size |
:378.3 KB
|
| Last updated |
:Jan 27, 2015 |
| Downloads |
: 409 |
Total downloads since Jan 27, 2015 : 409
|
|
| 本文公開日 |
|
| タイトル |
| タイトル |
An algorithm for finding a common basis of two matroids
|
| カナ |
|
| ローマ字 |
|
|
| 別タイトル |
|
| 著者 |
| 名前 |
山本, 芳嗣
|
| カナ |
ヤマモト, ヨシツグ
|
| ローマ字 |
Yamamoto, Yoshitsugu
|
| 所属 |
Dept. of Administration Engineering Keio University
|
| 所属(翻訳) |
|
| 役割 |
|
| 外部リンク |
|
|
| 版 |
|
| 出版地 |
|
| 出版者 |
| 名前 |
慶応義塾大学工学部
|
| カナ |
ケイオウ ギジュク ダイガク コウガクブ
|
| ローマ字 |
Keio gijuku daigaku kogakubu
|
|
| 日付 |
| 出版年(from:yyyy) |
1976
|
| 出版年(to:yyyy) |
|
| 作成日(yyyy-mm-dd) |
|
| 更新日(yyyy-mm-dd) |
|
| 記録日(yyyy-mm-dd) |
|
|
| 形態 |
|
| 上位タイトル |
| 名前 |
Keio engineering reports
|
| 翻訳 |
|
| 巻 |
29
|
| 号 |
4
|
| 年 |
1976
|
| 月 |
6
|
| 開始ページ |
41
|
| 終了ページ |
51
|
|
| ISSN |
|
| ISBN |
|
| DOI |
|
| URI |
|
| JaLCDOI |
|
| NII論文ID |
|
| 医中誌ID |
|
| その他ID |
|
| 博士論文情報 |
| 学位授与番号 |
|
| 学位授与年月日 |
|
| 学位名 |
|
| 学位授与機関 |
|
|
| 抄録 |
A matroid is an axiomization of linear independence of column vectors of a matrix. It was first described by WHITNEY (1935) (TUTTE 1965; HARARY and WELSH 1969; WILSON 1973). This paper proposes an algorithm for finding a common basis of two matroids, M1=(E, ■1) and M2=(E, ■2), for which several algorithms have been proposed (IRI and TOMIZAWA 1976; GREENE and MAGNANTI 1975; LAWLER 1975). The algorithm generates a sequence of pairs of bases of M1 and independent sets of the dual matroid ■ of M2, which increases the cardinality of their union. It will be shown that just one of the following cases occurs when this process does not generate such a sequence any more:
(i) A pair whose union is E is obtained so that the corresponding basis of M1 is a common basis,
(ii) M1 and M2 have no common basis.
This algorithm can be considered as a modification of EDMONDS' algorithm (EDMONDS 1968) in IRI and TOMIZAWA's manner (IRI and TOMIZAWA 1976).
|
|
| 目次 |
|
| キーワード |
|
| NDC |
|
| 注記 |
|
| 言語 |
|
| 資源タイプ |
|
| ジャンル |
| Departmental Bulletin Paper
|
|
| 著者版フラグ |
|
| 関連DOI |
|
| アクセス条件 |
|
| 最終更新日 |
|
| 作成日 |
|
| 所有者 |
|
| 更新履歴 |
|
| インデックス |
|
| 関連アイテム |
|
