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

DOI10.1007/978-3-319-42634-1_5zbMATH Open1437.05165arXiv1506.01695OpenAlexW2963714030MaRDI QIDQ1986558FDOQ1986558

Authors: Bireswar Das, Murali Krishna Enduri, I. Vinod Reddy 

Publication date: 8 April 2020

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

Abstract: The clique-width is a measure of complexity of decomposing graphs into certain tree-like structures. The class of graphs with bounded clique-width contains bounded tree-width graphs. We give a polynomial time graph isomorphism algorithm for graphs with clique-width at most three. Our work is independent of the work by Grohe et al. cite{grohe2015isomorphism} showing that the isomorphism problem for graphs of bounded clique-width is polynomial time.

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

Recommendations

• Polynomial-time algorithm for isomorphism of graphs with clique-width at most three
• Polynomial-time recognition of clique-width \(\leq 3\) graphs
• scientific article; zbMATH DE number 1512682
• Polynomial isomorphism algorithm for graphs which do not pinch to \(K_{3,g}\)
• scientific article; zbMATH DE number 3878378
• Graph isomorphism in quasipolynomial time (extended abstract)
• Graph-theoretic algorithms for the ``isomorphism of polynomials problem
• Graph isomorphisms in quasi-polynomial time [after Babai and Luks, Weisfeiler-Leman,\ldots]
• Isomorphism testing via polynomial-time graph extensions
• Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs

zbMATH Keywords

algorithmclique-widthgraph isomorphism

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• Polynomial-time algorithm for isomorphism of graphs with clique-width at most three
• Title not available (Why is that?)
• Polynomial-time recognition of clique-width \(\leq 3\) graphs
• The Weisfeiler-Leman dimension of distance-hereditary graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1986558)