Polynomial-time algorithm for isomorphism of graphs with clique-width at most three

DOI10.1016/j.tcs.2017.09.013zbMath1437.05165arXiv1506.01695OpenAlexW2963714030MaRDI QIDQ1986558

Bireswar Das, I. Vinod Reddy, Murali Krishna Enduri

Publication date: 8 April 2020

Published in: Theoretical Computer Science, Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1506.01695

zbMATH Keywords

algorithmclique-widthgraph isomorphism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (2)

The Weisfeiler-Leman dimension of distance-hereditary graphs ⋮ Polynomial-time algorithm for isomorphism of graphs with clique-width at most three

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial-time recognition of clique-width \(\leq 3\) graphs
• Testing branch-width
• Recent developments on graphs of bounded clique-width
• Does co-NP have short interactive proofs ?
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Modular decomposition and transitive orientation
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Polynomial-time algorithm for isomorphism of graphs with clique-width at most three
• Handle-rewriting hypergraph grammars
• Approximating clique-width and branch-width
• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Clique-Width is NP-Complete
• A Combinatorial Decomposition Theory
• Decomposition of Directed Graphs
• An O(n2) Algorithm for Undirected Split Decomposition
• Logspace and FPT Algorithms for Graph Isomorphism for Subclasses of Bounded Tree-Width Graphs
• Graph isomorphism in quasipolynomial time [extended abstract]
• Transitiv orientierbare Graphen

This page was built for publication: Polynomial-time algorithm for isomorphism of graphs with clique-width at most three