The Weisfeiler-Lehman Procedure
Abstract
Perhaps the oldest algorithmic technique used for the Graph Isomorphism
prob-lem is the Weisfeiler-Lehman procedure. Invented in the late 1960’s, it
has attracted research in several directions over the last five decades, and
continues to be an actively researched topic. Algorithmists invariably use this
procedure in combination with others tools for Graph Isomorphism. Logicians
interested in descriptive complexity have found logical characterizations for it.
There is a linear programming connection to the Weisfeiler-Lehman procedure,
and the Sherali-Adams hierarchy for the natural LP relaxation of a 0-1
integer linear pro-gram for Graph Isomorphism turns out to be intimately connected
to ”higher dimensional” versions of the procedure.
This brief essay, meant as an invitation to the topic, will touch upon these
as-pects of the Weisfeiler-Lehman procedure. However, it is by no means a
complete survey.
prob-lem is the Weisfeiler-Lehman procedure. Invented in the late 1960’s, it
has attracted research in several directions over the last five decades, and
continues to be an actively researched topic. Algorithmists invariably use this
procedure in combination with others tools for Graph Isomorphism. Logicians
interested in descriptive complexity have found logical characterizations for it.
There is a linear programming connection to the Weisfeiler-Lehman procedure,
and the Sherali-Adams hierarchy for the natural LP relaxation of a 0-1
integer linear pro-gram for Graph Isomorphism turns out to be intimately connected
to ”higher dimensional” versions of the procedure.
This brief essay, meant as an invitation to the topic, will touch upon these
as-pects of the Weisfeiler-Lehman procedure. However, it is by no means a
complete survey.
Full Text:
PDFRefbacks
- There are currently no refbacks.