Stable Matchings in Trees

スポンサーリンク

概要

• 論文の詳細を見る

• The maximum stable matching problem (Max-SMP) and the minimum stable matching problem (Min-SMP) have been known to be NP-hard for bipartite graphs, while Max-SMP can be solved in polynomial time for a bipartite graph G with degG(v)≦ 2 for any v∈X, where (X, Y) is a bipartition of G. This paper shows that both Max-SMP and Min-SMP can be solved in linear time for trees. This is the first polynomially solvable case for Min-SMP, as far as the authors know.

• 2013-10-30

著者

• Satoshi Tayu

  Department Of Communications And Integrated Systems Tokyo Institute Of Technology

• Shuichi Ueno

  Department of Communication and Computer Engineering, Tokyo Institute of Technology

関連論文

• On Two-Directional Orthogonal Ray Graphs
• Representation of Bipartite Graphs by OBDDs
• A Note on Two-Directional Orthogonal Ray Graphs and Related Graphs
• [招待講演]Orthogonal Ray Graphs with Applications to Nanocircuit Design
• Stable Matchings in Trees

スポンサーリンク