Polynomial-time Algorithm for Isomorphism of Graphs with Clique-width at most Three

June 04, 2015 · The Ethereal · 🏛 International Computing and Combinatorics Conference

🔮 THE ETHEREAL: The Ethereal
Pure theory — exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Bireswar Das, Murali Krishna Enduri, I. Vinod Reddy arXiv ID 1506.01695 Category cs.CC: Computational Complexity Cross-listed cs.DS Citations 4 Venue International Computing and Combinatorics Conference Last Checked 2 months ago
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.
Community shame:
Not yet rated
📄 View on arXiv 🌐 View on ar5iv 📑 PDF 🎉 Report Code Found
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

📜 Similar Papers

In the same crypt — Computational Complexity