%%% ====================================================================
%%%  @LaTeX-file{
%%%     filename  = "alonyz95.ltx",
%%%     date      = "16 May 1996",
%%%     time      = "15:06:26 EDT",
%%%     author    = "David M. Jones",
%%%     email     = "jacm@theory.lcs.mit.edu",
%%%     url       = "http://theory.lcs.mit.edu/~jacm/",
%%%     address   = "Journal of the ACM
%%%                  MIT Laboratory for Computer Science
%%%                  Room NE43-316
%%%                  545 Technology Square
%%%                  Cambridge, MA 02139
%%%                  USA",
%%%     telephone = "(617) 253-5936",
%%%     FAX       = "(617) 253-3480",
%%%     checksum  = "60856 105 565 4313",
%%%     codetable = "ISO/ASCII",
%%%     supported = "yes",
%%%     docstring = "Copyright (c) 1995 by ACM, Inc.
%%%                  Permission to make digital or hard copies of part
%%%                  or all of this work for personal or classroom use
%%%                  is granted without fee provided that copies are
%%%                  not made or distributed for profit or direct
%%%                  commercial advantage and that copies bear this
%%%                  notice and the full citation on the first page.
%%%                  Copyrights for components of this work owned by
%%%                  others than ACM must be honored. Abstracting with
%%%                  credit is permitted. To copy otherwise, to
%%%                  republish, to post on servers, or to redistribute
%%%                  to lists, requires prior specific permission
%%%                  and/or a fee. Request permissions from
%%%                  Publications Dept, ACM Inc., fax +1 (212)
%%%                  869-0481, or permissions@acm.org.
%%%
%%%                  This is a LaTeX2e file.  To process it, you will
%%%                  need a copy of the acmabs document class, which is
%%%                  available via the following URL:
%%%
%%%                  http://theory.lcs.mit.edu/~jacm/acmart/acmabs.cls
%%%                  ",
%%%  }
%%% ====================================================================

\documentclass{acmabs}

\begin{document}

\Journal{Journal of the ACM}

\refkey{AlonYZ95}

\title{Color-coding}

\author{Noga Alon \and Raphael Yuster \and Uri Zwick}

\Pages{844--856}

\Month{July}

\Year{1995}

\Volume{42}

\Number{4}

\maketitle

\begin{abstract}

We describe a novel randomized method, the method of \emph{color-coding} for
  finding simple paths and cycles of a specified length~$k$, and other small
  subgraphs, within a given graph $G = (V,E)$. The randomized algorithms
  obtained using this method can be derandomized using families of
  \emph{perfect hash functions}. Using the color-coding method we obtain, in
  particular, the following new results: \begin{itemize} \item For every
  fixed~$k$, if a graph $G = (V,E)$ contains a simple cycle of size
  \emph{exactly} $k$, then such a cycle can be found in either $O(V^\omega)$
  expected time or $O(V^\omega \log V)$ worst-case time, where $\omega < 2.376$
  is the exponent of matrix multiplication. (Here and in what follows we use
  $V$ and~$E$ instead of $|V|$ and~$|E|$ whenever no confusion may arise.)
  \item For every fixed~$k$, if a \emph{planar} graph $G = (V,E)$ contains a
  simple cycle of size \emph{exactly} $k$, then such a cycle can be found in
  either $O(V)$ expected time or $O(V \log V)$ worst-case time. The same
  algorithms applies, in fact, not only to planar graphs, but to any
  \emph{minor closed} family of graphs which is not the family of all graphs.
  \item If a graph $G = (V, E)$ contains a subgraph isomorphic to a
  \emph{bounded tree-width} graph $H = (V_H, E_H)$ where $|V_H| = O(\log V)$,
  then such a copy of~$H$ can be found in \emph{polynomial time}. This was not
  previously known even if $H$ were just a path of length $O(\log V)$.
  \end{itemize} These results improve upon previous results of many authors.
  The third result resolves in the affirmative a conjecture of Papadimitriou
  and Yannakakis that the LOG PATH problem is in~P\@. We can show that it is
  even in~NC.

\end{abstract}

\begin{categories}

G.2.2 [\textbf{Discrete Mathematics}]: Graph Theory---\emph{graph
algorithms}; \emph{path and circuit problems}

\end{categories}

\end{document}