Inverse problems of matroid intersection
文献类型：期刊论文
| 作者 | Cai, MC |
| 刊名 | JOURNAL OF COMBINATORIAL OPTIMIZATION
 |
| 出版日期 | 1999-12-01 |
| 卷号 | 3期号:4页码:465-474 |
| 关键词 | Inverse problem matroid intersection minimum cost circulation strongly polynomial algorithm |
| ISSN号 | 1382-6905 |
| 英文摘要 | In this paper we study the inverse problem of matroid intersection: Two matroids M-1 = (E, I-1) and M-2 = (E, I-2), their intersection B, and a weight function w on E are given. We try to modify weight w, optimally and with bounds, such that B becomes a maximum weight intersection under the modified weight. It is shown in this paper that the problem can be formulated as a combinatorial linear program and can be further transformed into a minimum cost circulation problem. Hence it can be solved by strongly polynomial time algorithms. We also give a necessary and sufficient condition for the feasibility of the problem. Finally we extend the discussion to the version of the problem with Multiple Intersections. |
| 语种 | 英语 |
| WOS记录号 | WOS:000084252700008 |
| 出版者 | KLUWER ACADEMIC PUBL |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/14504]  |
| 专题 | 中国科学院数学与系统科学研究院 |
| 通讯作者 | Cai, MC |
| 作者单位 | Acad Sinica, Inst Syst Sci, Beijing 100080, Peoples R China |
| 推荐引用方式 GB/T 7714 | Cai, MC. Inverse problems of matroid intersection[J]. JOURNAL OF COMBINATORIAL OPTIMIZATION,1999,3(4):465-474. |
| APA | Cai, MC.(1999).Inverse problems of matroid intersection.JOURNAL OF COMBINATORIAL OPTIMIZATION,3(4),465-474. |
| MLA | Cai, MC."Inverse problems of matroid intersection".JOURNAL OF COMBINATORIAL OPTIMIZATION 3.4(1999):465-474. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。