The number of depth-first searches of an ordered set

DOI10.1007/BF00563529zbMath0695.06002OpenAlexW1969845931MaRDI QIDQ909681

Henry A. Kierstead, William T. jun. Trotter

Publication date: 1989

Published in: Order (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00563529

zbMATH Keywords

NP-completeNP- hardgreedy linear extensionsdepth-first linear extensions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Partial orders, general (06A06)

Related Items (4)

Planar posets, dimension, breadth and the number of minimal elements ⋮ A linear algorithm to decompose inheritance graphs into modules ⋮ Greedy balanced pairs in \(N\)-free ordered sets ⋮ Counting linear extensions

Cites Work

• Unnamed Item
• NP-completeness results concerning greedy and super greedy linear extensions
• The complexity of theorem-proving procedures

This page was built for publication: The number of depth-first searches of an ordered set