The number of depth-first searches of an ordered set |
| |
| Authors: | H A Kierstead W T Trotter |
| |
| Institution: | (1) Department of Mathematics, Arizona State University, 85287 Tempe, AZ, U.S.A. |
| |
| Abstract: | We show that the problems of deciding whether an ordered set has at leastk depth-first linear extensions and whether an ordered set has at leastk greedy linear extensions are NP-hard.Supported by Office of Naval Research contract N00014-85K-0494.Supported by National Science Foundation grant DMS-8713994. |
| |
| Keywords: | 06A10 68C25 |
| 本文献已被 SpringerLink 等数据库收录！ |
