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

zbMATH Keywords

subgraph isomorphismparameterized complexityminor-free graphs

Mathematics Subject Classification ID

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)

Extended MSO model checking via small vertex integrity ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity

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