[Nauty] Suggested Reading

[Mark Goldberg]

>>
> I am an undergraduate research assistant starting on a project to use
> Nauty.  I was wondering if anyone had any suggested readings on canonical
> labelling of graphs etc.. to ge me started.  Thanks for the help.
>
> Nathaniel


You can start with this. Probably, some references are missed.
My apologies.

-Mark

\rf{
[AHU] A. V. Aho, J. E. Hopcroft, and J.D. Ullman, The Design and Analysis 
of Computer Algorithms, Addison-Wesley, 1974.
}

\rf{
[Ba80] L. Babai, P. Erd\"os, and S. M. Selkov, Random graph isomorphism,
{\sl SIAM J. of Computing} (1980), Vol. 9,  628--635.
}

\rf{
[Ba82] L. Babai, D. Yu. Grigoryev, and D. M. Mount, Isomorphism of graphs 
with bounded multiplicity, 
{\sl Proceedings 14th Ann. ACM Symp. Theory of Computing} (1982), 310--324.
}

\rf{
[Ba83] L. Babai and E. M. Luks, Canoncal labeling of graphs,
{\sl Proceedings 15th Ann. ACM Symp. Theory of Computing} (1983),  171--183.
}

\rf{
[Bo78] K. S. Booth, Isomorphism testing for graphs, semigroups and finite
automata are polynomially equivalent, {\sl SIAM J. Computing}, 7, (1978),
273--279.
}

\rf{
[Co78] M. J. Colbourn and C. J. Colbourn, Graph isomorphism and self-complementary graphs, {\sl SIGACT News}, 10, (1978), 25--29.
}

\rf{
[Co81] M. J. Colbourn and K. S. Booth, Linear time automorphism algorithm 
for trees, interval graphs, and planar graphs, {\sl SIAM J. Computing}, 10,
(1981), 203--225.
}


\rf{
[Co70] D. G. Corneil and C. C. Gotlieb, An efficient algorithm for graph
isomorphism, {\sl J. ACM} (1970), Vol 17, 51--64.
}

\rf{
[Co84] D. Corneil and M. Goldberg, A Non-Factorial Algorithm for 
Canonical Numbering of a Graph,
{\sl J. Algorithms} Vol. 5, (1984),  345--362.
}

\rf
{[De77] N. Deo, J. M. Davis, and R. E. Lord, A new algorithm for 
digraph isomorphism, {\sl BIT}, (17), (1977), 16--30.
}

\rf
{[Fi80] I. S. Filotti and J. N. Mayer, A polynomial algorithm for determining 
the isomorphism of graphs of fixed genus, {\sl Proceedings 12th Ann. ACM Symp. 
Theory of Computing}, 17, (1980), 236--243,
}

\rf{
[F\"u83] M. F\"urer, W. Schnyder, and E. Specker,
Normal forms for trivalent graphs and graphs of bounded valency,
{\sl Proceedings 15th Ann. ACM Symp. Theory of Computing}, (1983),
161--170.
}

\rf{
[Fu80] M. Furst, J. Hopcroft, and E. Luks,
A subexponential algorithm for trivalent graph isomorphism, 
{\sl Proceedings 11th Southesatern Conference on Combinatorics, Graph
Theory, and Computing}, (1980);in Congressum Numerantium, 33,
36--41.
}

\rf{
[Fu80] M. Furst, J. Hopcroft, and E. Luks,
Polynomial time algorithms for permutation groups, 
{\sl Proceedings 21th IEEE Symp. on Foundations Computer Science}, (1980),
36--41.
}

\rf{
[Ga87] Z. Galil, C. M. Hoffman, E. M. Luks, C. P. Schnorr, and 
A. Weber], An $O(n^3 \log n)$ deterministic and $O(n^3)$ probabilistic 
isomorphism test for trivalent graphs, {\sl J. ACM}, 34, (1987), 513--531.
}

\rf{
[Go83] M. Goldberg, A Non-Factorial Algorithm for the Graph 
Isomorphism Problem,
{\sl Discrete Applied Mathematics} Vol. 6, (1983),  229--236.
}

\rf{
[Ha82] F. Harary, M. Plantholt, and R. Statman, The graph
isomorphism problem is polynomially equivalent to the legitimate
deck problem for regular graphs, {\sl Carib\-bean J. Math.}
1(1) (1982),  15--23.}

\rf
{[Ho74] J. E. Hopcroft and C. K. Wong, Linear Time algorithms for 
isomorphism of planar graphs, {\sl Proceedings 6th Ann. ACM Symp. 
Theory of Computing}, (1974), 172--184.
}

\rf{
[Ho82] C. M. Hoffman, Group-Theoretic Algorithms and Graph Isomorphism,
{\sl Lectures Notes in Computer Science}, 136, (1982), Springer.
}

\rf{
[JvLe99] J. van Leeuwen, in {\sl Handbook of Theoretical Computer Science} 
Chapter 10, Graph Algorithms, (1994), Elsevier Scienceu 525--631.
}

\rf{
[Kl02] A. Klivans and D. van Melkebeek,
Graph Nonisomorphism has Subexponential Size Proof Unless the Polynomial-Time 
Hierarchy Collapses, {\sl SIAM J. Computing}, 31, (2002), 1501--1526.
}

\rf{
[K\"o93] J. K\"obler, U. Sch\"oning, and J. Tor\'an, {\sl
The Graph Isomorphism Problem: Its Structural Complexity},
Birkh\"auser, 1993.}

\rf{
[Kr94] D. Kratsch and L. A. Hemaspaandra, On the complexity
of graph reconstruction, {\sl Math. Systems Theory}
27(3) (1994), 257--273.}

\rf{
[Kr02] I. Krasikov, A. Lev, and B.D. Thatte, Upper bounds
on the automorphism group of a graph, {\sl Discrete Math.}
256 (2002), 489--493.
}

\rf{
[Lu82] E. M. Luks, {Isomorphism of graphs of bounded valence can be tested
in polynomial time}, {\sl J. Comput. System Sci.}, 25, (1982), 42--65.
}

\rf{
[Lu81] A. Lubiw, Some NP-complete problems similar to graph isomorphism,
{\sl SIAM J. Computing} Vol. 10, (1981),  11--24.
}

\rf{
[Ma82] A. Mansfield, The relationship between the
computational complexities of the legitimate deck and isomorphism
problems, {\sl Quart. J. Math. Oxford (2)} 33 (1982), 345--347.
} 

\rf{
[Ma79] R. Mathon, ``A note on the graph isomorphism counting problem'',
{\sl Information Processing Letters}, Vol. 8, No.3 (1979), 131--132.
}

\rf{
[Mc81] B. D. McKay, Practical Graph Isomorphism, {\sl Congressus Numerantium},
30, (1981), 45--87.
}

\rf{
[Mi80], G. Miller, Isomorphism testing for graphs of bounded genus,
{\sl Proceedings 12th Ann. ACM Symp. Theory of Computing},
17, (1980), 225--235.
}

\rf{
[We68], B. Weisfeiler and A.A. Leman, Reduction of a graph to a canonical
form and an algebra arizing during this reduction,
{\sl Nauchno-Technicheskaya Informatsia}, 9, Ser. 2, (1968), 12--16.
}
\rf
{[We79], B. Weisfeiler, (ed.) On construction and identifacation of graphs,
{\sl Lecture Notes in Mathematics}, 558, Springer, Berlin, (1976).
}