arXiv Analytics

Sign in

arXiv:0710.2268 [math.CO]AbstractReferencesReviewsResources

Complexity of some Path Problems in DAGs and Linear Orders

Serge Burckel

Published 2007-10-11Version 1

We investigate here the computational complexity of three natural problems in directed acyclic graphs. We prove their NP Completeness and consider their restrictions to linear orders.

Comments: 5 pages, 3 figures
Categories: math.CO, cs.IT, math.IT
Related articles: Most relevant | Search more
arXiv:2408.17067 [math.CO] (Published 2024-08-30)
Stable matchings, choice functions, and linear orders
arXiv:1903.07569 [math.CO] (Published 2019-03-18)
The size of the largest antichains in products of linear orders
arXiv:1604.00612 [math.CO] (Published 2016-04-03)
A note on extremal results on directed acyclic graphs

Links

Toolbox