Complexity of some Path Problems in DAGs and Linear Orders

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.
5 pages, 3 figures

Keywords

Combinatorics, Information Theory

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/139847

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0710.2268
 http://arxiv.org/abs/0710.2268

Collections

arXiv