References

Overview of all references, both (partially) read and unread.

Read with extended notes

• A Logspace Algorithm for Partial 2-Tree Canonization (2008)
• A partial k-arboretum of graphs with bounded treewidth (1998)
• A unifying method for the design of algorithms canonizing combinatorial objects (2019)
• An Improved Isomorphism Test for Bounded-tree-width Graphs (2020)
• Attacks On Difficult Instances Of Graph Isomorphism: Sequential And Parallel Algorithms (2009)
• Canonical representations of partial 2- and 3-trees (1992)
• Canonizing Graphs of Bounded Tree Width in Logspace (2017)
• Practical graph isomorphism, II (2014)
• Scott A method for representing graphs as rooted trees for graph canonization (2019)
• The isomorphism problem for k-trees is complete for logspace (2012)

Read

• Engineering an efficient canonical labeling tool for large and sparse graphs (2007)
• Conauto-2.0: Fast Isomorphism Testing and Automorphism Group Computation (2011)
• Graph isomorphism in quasipolynomial time parameterized by treewidth (2020)
• Graphs of Bounded Treewidth Can Be Canonized in AC¹ (2011)
• Language-aware Indexing for Conjunctive Path Queries (2022)
• Novel Techniques for Automorphism Group Computation (2013)
• Saucy3: Fast Symmetry Discovery in Graphs (2012)
• Canonical Forms for General Graphs Using Rooted Trees - Correctness and Complexity Study of the SCOTT Algorithm (2020)
• The Space Complexity of k-Tree Isomorphism (2007)
• Search Space Contraction in Canonical Labeling of Graphs (2008)

Unread but maybe good to read

• Isomorphism Testing via Polynomial-Time Graph Extensions (2011)
• The Complexity of McKay's Canonical Labeling Algorithm (1995)
• Planar Graph Isomorphism is in Log-Space (2009)

Unread only for reference

• A logspace algorithm for tree canonization (1992)
• Arbres et processus de Galton-Watson (1986)
• Compressed Tree Canonization (2015)
• Directed Tree-Width (2001)
• Graph Isomorphism in Quasipolynomial Time (2016)
• Graph minors. II. Algorithmic aspects of tree-width (1986)
• Nonserial Dynamic Programming (1972)
• On the dimension of a graph (1965)
• S-functions for graphs (1976)

Other

• MIT Advanced Algorithms Lecture 15 on treewidth and elimination orderings by David Karger (2004)
• Lecture 11 “Treewidth” from 2WO08 Computational Topology by Jeff Erickson (2015)
• Lecture 9 “Treewidth” from 2IMA25 Exact Algorithms for NP-hard Problems by Bart Jansen (2022)
• Roan Hofland. Conjunctive Path Query Generation for Benchmarking (2022)
• Wikipedia on Treewidth
• Wikipedia on Tree decomposition
• Wikipedia on Chordal completion
• Wikipedia on Partial k-tree
• Wikipedia on Haven
• Wikipedia on Bramble
• Wikipedia on Set cover problem
• Wikipedia on Graph coloring
• Computer Science Stack Exchange, “Converting a digraph to an undirected graph in a reversible way” (2014)
• Brendan D. McKay, Adolfo Piperno. nauty and Traces User’s Guide (Version 2.7), September, 2021
• Nauty mailing list “Labeled graphs” (2013)
• Nauty mailing list “canonical label for directed graphs” (2005)
• Nauty mailing list “Can we do colored edges in nauty?” (2005)
• Nauty mailing list “digraph–>graph” (2013)
• Nauty mailing list “canonical label for directed graphs” (2005)
• Nauty mailing list “Re: nauty-list digest, Vol 1 #116 - 3 msgs” (2005)
• The website for bliss “bliss: A Tool for Computing Automorphism Groups and Canonical Labelings of Graphs”
• The website for nishe “A canonical labeling and symmetry detecting algorithm for graphs”
• The website for “conauto Graph Isomorphism Algorithm conauto”
• The website for saucy “Saucy3: Fast Symmetry Discovery in Graphs”
• The website for GI-EXT “GI-EXT: Graph Isomorphism using EXTended graphs”
• The website for Scott “Structure Canonisation using Ordered-Tree Translation”
• The old website for nauty and Traces
• The website for nauty and Traces
• Computational Combinatorics “Canonical Labelings with Nauty” by Derrick Stolee (2012)