Longest paths in Planar DAGs in Unambiguous Logspace

Simple item page
dc.creatorLimaye, Nutan
dc.creatorMahajan, Meena
dc.creatorNimbhorkar, Prajakta
dc.date2008-02-12
dc.date.accessioned2026-07-07T09:20:17Z
dc.date.available2026-07-07T09:20:17Z
dc.descriptionWe show via two different algorithms that finding the length of the longest path in planar directed acyclic graph (DAG) is in unambiguous logspace UL, and also in the complement class co-UL. The result extends to toroidal DAGs as well.
dc.identifierhttps://arxiv.org/abs/0802.1699
dc.identifierhttp://arxiv.org/abs/0802.1699
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/154675
dc.subjectComputational Complexity
dc.titleLongest paths in Planar DAGs in Unambiguous Logspace
dc.typetext

Files

Collections

arXiv