Abstract | ||
---|---|---|
We give some lower bounds on the certificate complexity of some problems concerning stable marriage, answering a question of Gusfield and Irving. |
Year | DOI | Venue |
---|---|---|
2004 | 10.1016/j.ipl.2004.09.006 | Inf. Process. Lett. |
Keywords | Field | DocType |
stable marriage,certificate complexity,combinatorial problems,lower bound,computational complexity | Discrete mathematics,Stable marriage problem,Question answering,Information processing,Upper and lower bounds,Theoretical computer science,Artificial intelligence,Certification,Mathematics,Computational complexity theory,Certificate | Journal |
Volume | Issue | ISSN |
92 | 6 | 0020-0190 |
Citations | PageRank | References |
0 | 0.34 | 3 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Daniel J. Dougherty | 1 | 413 | 32.13 |
Stanley M. Selkow | 2 | 431 | 72.37 |