On the complexity of finding iso- and other morphisms for partial \(k\)- trees
From MaRDI portal
Publication:1201267
DOI10.1016/0012-365X(92)90687-BzbMath0764.68128OpenAlexW2076043677MaRDI QIDQ1201267
Publication date: 17 January 1993
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0012-365x(92)90687-b
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (55)
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering ⋮ Approximation algorithms for classes of graphs excluding single-crossing graphs as minors ⋮ Finding the maximum common subgraph of a partial \(k\)-tree and a graph with a polynomially bounded number of spanning trees ⋮ Tree-edges deletion problems with bounded diameter obstruction sets ⋮ Detecting induced star-like minors in polynomial time ⋮ Sequential and parallel algorithms for embedding problems on classes of partial k-trees ⋮ On Chen and Chen's new tree inclusion algorithm ⋮ Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs ⋮ On the distance and multidistance graph embeddability problem ⋮ Constructive linear time algorithms for branchwidth ⋮ Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth ⋮ On maximum common subgraph problems in series-parallel graphs ⋮ Detecting induced minors in AT-free graphs ⋮ Maximum tree-packing in time \(O(n^{5/2})\) ⋮ Maximum tree-packing in time O(n5/2) ⋮ On complexity of multidistance graph recognition in \(\mathbb{R}^1\) ⋮ Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs ⋮ Probabilistic and exact frequent subtree mining in graphs beyond forests ⋮ Mineurs d'arbres avec racines ⋮ On graph contractions and induced minors ⋮ Edge contractions in subclasses of chordal graphs ⋮ Contracting planar graphs to contractions of triangulations ⋮ Enumerating Grid Layouts of Graphs ⋮ A note on block-and-bridge preserving maximum common subgraph algorithms for outerplanar graphs ⋮ Subgraph isomorphism in graph classes ⋮ Maximum common induced subgraph parameterized by vertex cover ⋮ Maximum packing for biconnected outerplanar graphs ⋮ Faster parameterized algorithms for minor containment ⋮ Fixed-parameter tractability for the Tree Assembly problem ⋮ Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time ⋮ The complexity of subgraph isomorphism for classes of partial k-trees ⋮ Edge Contractions in Subclasses of Chordal Graphs ⋮ On retracts, absolute retracts, and foldings in cographs ⋮ Detecting fixed patterns in chordal graphs in polynomial time ⋮ A note on the subgraphs of the (\(2\times \infty \))-grid ⋮ Parameterized graph cleaning problems ⋮ Embeddings of \(k\)-connected graphs of pathwidth \(k\) ⋮ A survey on tree edit distance and related problems ⋮ Efficient frequent connected subgraph mining in graphs of bounded tree-width ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The edge-disjoint paths problem is NP-complete for series-parallel graphs ⋮ An algebraic view of the relation between largest common subtrees and smallest common supertrees ⋮ Subgraph isomorphism on graph classes that exclude a substructure ⋮ New and improved algorithms for unordered tree inclusion ⋮ Approximating the maximum clique minor and some subgraph homeomorphism problems ⋮ The complexity of the vertex-minor problem ⋮ A Multi-labeled Tree Edit Distance for Comparing "Clonal Trees" of Tumor Progression. ⋮ Mine ’Em All: A Note on Mining All Graphs ⋮ Containment relations in split graphs ⋮ Unnamed Item ⋮ An exact algorithm for subgraph homeomorphism ⋮ Constrained tree inclusion ⋮ FINDING SMALLEST SUPERTREES UNDER MINOR CONTAINMENT ⋮ Improved Hardness of Maximum Common Subgraph Problems on Labeled Graphs of Bounded Treewidth and Bounded Degree
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
This page was built for publication: On the complexity of finding iso- and other morphisms for partial \(k\)- trees
