HOW DO I MARRY THEE - LET ME COUNT THE WAYS

被引：16

作者：

BENJAMIN, AT ^{[1
]}

CONVERSE, C ^{[1
]}

KRIEGER, HA ^{[1
]}

机构：

[1] CALIF STATE UNIV FULLERTON,DEPT MATH,FULLERTON,CA 92634

来源：

DISCRETE APPLIED MATHEMATICS | 1995年 / 59卷 / 03期

关键词：

D O I：

10.1016/0166-218X(94)00129-2

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A stable marriage problem of size 2n is constructed which contains Theta(2(n) root n) stable matchings. This construction provides a new lower bound on the maximum number of stable matchings for problems of even size and is comparable to a known lower bound when the size is a power of 2. The method of construction makes use of special properties of the latin marriage problem, which we develop.

引用

页码：285 / 292

页数：8