|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Sherali-Adams Relaxations of Graph Isomorphism Polytopes | | Peter N. Malkin
; | | Date: |
4 Jul 2011 | | Abstract: | We investigate the Sherali-Adams lift & project hierarchy applied to a graph
isomorphism polytope whose integer points encode the isomorphisms between two
graphs. In particular, the Sherali-Adams relaxations characterize a new vertex
classification algorithm for graph isomorphism, which we call the generalized
vertex classification algorithm. This algorithm generalizes the classic vertex
classification algorithm and generalizes the work of Tinhofer on polyhedral
methods for graph automorphism testing. We establish that the Sherali-Adams
lift & project hierarchy when applied to a graph isomorphism polytope needs
Omega(n) iterations in the worst case before converging to the convex hull of
integer points. We also show that this generalized vertex classification
algorithm is also strongly related to the well-known Weisfeiler-Lehman
algorithm, which we show can also be characterized in terms of the
Sherali-Adams relaxations of a semi-algebraic set whose integer points encode
graph isomorphisms. | | Source: | arXiv, 1107.0632 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER