{
  "id": "0710.2268",
  "version": "v1",
  "published": "2007-10-11T15:00:45.000Z",
  "updated": "2007-10-11T15:00:45.000Z",
  "title": "Complexity of some Path Problems in DAGs and Linear Orders",
  "authors": [
    "Serge Burckel"
  ],
  "comment": "5 pages, 3 figures",
  "categories": [
    "math.CO",
    "cs.IT",
    "math.IT"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2007-10-11T15:00:45.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "linear orders",
      "path problems",
      "computational complexity",
      "natural problems",
      "directed acyclic graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 5,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2007arXiv0710.2268B"
    }
  }
}