The number of depth-first searches of an ordered set

Henry Kierstead; W. T. Trotter

doi:10.1007/BF00563529

The number of depth-first searches of an ordered set

Henry Kierstead, W. T. Trotter

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

We show that the problems of deciding whether an ordered set has at least k depth-first linear extensions and whether an ordered set has at least k greedy linear extensions are NP-hard.

Original language	English (US)
Pages (from-to)	295-303
Number of pages	9
Journal	Order
Volume	6
Issue number	3
DOIs	https://doi.org/10.1007/BF00563529
State	Published - Sep 1 1989

Keywords

AMS subject classifications (1980): 06A10, 68C25
Depth-first linear extension
NP-complete
greedy linear extension
ordered set

ASJC Scopus subject areas

Algebra and Number Theory
Geometry and Topology
Computational Theory and Mathematics

Access to Document

10.1007/BF00563529

Cite this

@article{84116637b0324806a87a7d3823741054,

title = "The number of depth-first searches of an ordered set",

abstract = "We show that the problems of deciding whether an ordered set has at least k depth-first linear extensions and whether an ordered set has at least k greedy linear extensions are NP-hard.",

keywords = "AMS subject classifications (1980): 06A10, 68C25, Depth-first linear extension, NP-complete, greedy linear extension, ordered set",

author = "Henry Kierstead and Trotter, {W. T.}",

year = "1989",

month = sep,

day = "1",

doi = "10.1007/BF00563529",

language = "English (US)",

volume = "6",

pages = "295--303",

journal = "Order",

issn = "0167-8094",

publisher = "Springer Netherlands",

number = "3",

}

TY - JOUR

T1 - The number of depth-first searches of an ordered set

AU - Kierstead, Henry

AU - Trotter, W. T.

PY - 1989/9/1

Y1 - 1989/9/1

N2 - We show that the problems of deciding whether an ordered set has at least k depth-first linear extensions and whether an ordered set has at least k greedy linear extensions are NP-hard.

AB - We show that the problems of deciding whether an ordered set has at least k depth-first linear extensions and whether an ordered set has at least k greedy linear extensions are NP-hard.

KW - AMS subject classifications (1980): 06A10, 68C25

KW - Depth-first linear extension

KW - NP-complete

KW - greedy linear extension

KW - ordered set

UR - http://www.scopus.com/inward/record.url?scp=34249976866&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34249976866&partnerID=8YFLogxK

U2 - 10.1007/BF00563529

DO - 10.1007/BF00563529

M3 - Article

AN - SCOPUS:34249976866

SN - 0167-8094

VL - 6

SP - 295

EP - 303

JO - Order

JF - Order

IS - 3

ER -

The number of depth-first searches of an ordered set

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this