Polynomial time algorithms for variants of graph matching on partial \(k\)-trees

DOI10.1515/fcds-2016-0010zbMath1378.05200OpenAlexW2526117656MaRDI QIDQ1692069

Takayuki Nagoya

Publication date: 26 January 2018

Published in: Foundations of Computing and Decision Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1515/fcds-2016-0010

zbMATH Keywords

polynomial time algorithmpartial \(k\)-treesgraph isomorphism with restriction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Computational complexity of computing a partial solution for the graph automorphism problems
• Laminar structure of ptolemaic graphs with applications
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Complexity of Finding Embeddings in a k-Tree
• The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
• Some NP-Complete Problems Similar to Graph Isomorphism
• On testing isomorphism of permutation graphs
• Subtree Isomorphism in O(n5/2)
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• Graph Classes: A Survey
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs