Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
type: Item
instance of: scholarly article
title: Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
zbMATH Open document ID: 1358.05284
DOI: 10.1137/140999980
author: Daniel Lokshtanov
author: Marcin Pilipczuk
author: Michał Pilipczuk
author: Saket Saurabh
published in: SIAM Journal on Computing
publication date: 2017-03-10T00:00:00Z
full work available at URL: https://arxiv.org/abs/1404.0818
full work available at URL: WRAP 1371795-cs-270115-tw-iso.pdf
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 68W05
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 6693778
zbMATH Keywords: graph isomorphism
zbMATH Keywords: bounded treewidth graphs
zbMATH Keywords: fixed-parameter tractability
zbMATH Keywords: canonization
MaRDI profile type: Publication
OpenAlex ID: W2593190625
arXiv ID: 1404.0818
cites work: Q4091421
cites work: Canonical representations of partial 2- and 3-trees
cites work: An introduction to clique minimal separator decomposition
cites work: Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
cites work: A partial k-arboretum of graphs with bounded treewidth
cites work: Necessary edges in \(k\)-chordalisations of graphs
cites work: On Tractable Parameterizations of Graph Isomorphism
cites work: Q4426346
cites work: Q3077955
cites work: Minimum bisection is fixed parameter tractable
cites work: Q5315023
cites work: Fundamentals of parameterized complexity
cites work: Parametrized complexity theory.
cites work: Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
cites work: Q3875946
cites work: A V log V algorithm for isomorphism of triconnected planar graphs
cites work: Q4148000
cites work: Q3549734
cites work: Treewidth. Computations and approximations
cites work: Isomorphism for Graphs of Bounded Feedback Vertex Set Number
cites work: Optimal decomposition by clique separators
cites work: Isomorphism of graphs of bounded valence can be tested in polynomial time
cites work: Isomorphism for Graphs of Bounded Connected-Path-Distance-Width
cites work: Reduction Techniques for Graph Isomorphism in the Context of Width Parameters
cites work: The isomorphism problem for classes of graphs closed under contraction
cites work: Graph minors. XIII: The disjoint paths problem
cites work: Graph minors. XVI: Excluding a non-planar graph
cites work: Graph isomorphism is in the low hierarchy
cites work: Decomposition by clique separators
cites work: Myhill-Nerode Methods for Hypergraphs
cites work: Isomorphism for graphs of bounded distance width
Recommended article: An Improved Isomorphism Test for Bounded-tree-width Graphs
Recommended article: An improved isomorphism test for bounded-tree-width graphs
Recommended article: Canonizing Graphs of Bounded Tree Width in Logspace
Recommended article: Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable (extended abstract)
Recommended article: Q4725763
Recommended article: On Tractable Parameterizations of Graph Isomorphism
Recommended article: Graphs of Bounded Treewidth Can Be Canonized in $\mbox{{\sf AC}$^1$}$
Recommended article: Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs
Recommended article: Restricted space algorithms for isomorphism on bounded treewidth graphs
description: scientific article