Research output: Contribution to journalArticlepeer-review

677 Scopus citations


These results improve upon previous results of many authors. The third result resolves in the affirmative a conjecture of Papadimltnou and Yannakakis that the LOG PATH problem is m P. We can show that it is even in NC.

Original languageEnglish (US)
Pages (from-to)844-856
Number of pages13
JournalJournal of the ACM (JACM)
Issue number4
StatePublished - Jul 1 1995
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence


  • Derandornization
  • perfect hashing
  • subgraph isomorphism
  • tree-width

Fingerprint Dive into the research topics of 'Color-Coding'. Together they form a unique fingerprint.

Cite this