On the complexity of finding iso- and other morphisms for partial \(k\)- trees

DOI10.1016/0012-365X(92)90687-BzbMath0764.68128MaRDI QIDQ1201267

Robin Thomas, Ji{ří} Matoušek

Publication date: 17 January 1993

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

complexity; polynomial algorithms; NP-complete; partial \(k\)-tree

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C05: Trees

68R10: Graph theory (including graph drawing) in computer science

05C38: Paths and cycles

05C10: Planar graphs; geometric and topological aspects of graph theory

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Related Items

Mineurs d'arbres avec racines, The complexity of subgraph isomorphism for classes of partial k-trees, Maximum tree-packing in time \(O(n^{5/2})\), Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs, Maximum packing for biconnected outerplanar graphs, Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time

Cites Work

• Unnamed Item
• Unnamed Item
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Graph minors. XIII: The disjoint paths problem
• Algorithms finding tree-decompositions of graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• On the Computational Complexity of Combinatorial Problems
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs