Subgraph isomorphism on graph classes that exclude a substructure
DOI10.1007/s00453-020-00737-zzbMath1492.68102arXiv1905.10670OpenAlexW2944913327MaRDI QIDQ5919029
Tesshu Hanaka, Yusuke Kobayashi, Hans L. Bodlaender, Yasuaki Kobayashi, Yota Otachi, Tom C. van der Zanden, Yoshio Okamoto
Publication date: 11 November 2020
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1905.10670
Graph theory (including graph drawing) in computer science (68R10) Graph minors (05C83) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding a chain graph in a bipartite permutation graph
- Sparsity. Graphs, structures, and algorithms
- Subgraph isomorphism in graph classes
- The complexity of subgraph isomorphism for classes of partial k-trees
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- On the computational complexity of vertex integrity and component order connectivity
- Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth
- Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs
- List edge multicoloring in graphs with few cycles
- Matching is as easy as matrix inversion
- An application of simultaneous diophantine approximation in combinatorial optimization
- On the complexity of finding iso- and other morphisms for partial \(k\)- trees
- Modular decomposition and transitive orientation
- The complexity of induced minors and related problems
- Algorithmic meta-theorems for restrictions of treewidth
- Subgraph isomorphism for biconnected outerplanar graphs in cubic time
- Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask).
- Integer Programming with a Fixed Number of Variables
- Planar Subgraph Isomorphism Revisited
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- Minkowski's Convex Body Theorem and Integer Programming
- Subtree Isomorphism in O(n5/2)
- Color-coding
- Subgraph Isomorphism in Planar Graphs and Related Problems
- Subexponential Time Algorithms for Embedding H-Minor Free Graphs
- Tight Lower Bounds on Graph Embedding Problems
- Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
- Parameterized Algorithms
This page was built for publication: Subgraph isomorphism on graph classes that exclude a substructure
