Induced subgraph isomorphism: are some patterns substantially easier than others?
From MaRDI portal
Publication:888440
DOI10.1016/j.tcs.2015.09.001zbMath1331.05154OpenAlexW1883038075MaRDI QIDQ888440
Eva-Marta Lundell, Mirosław Kowaluk, Andrzej Lingas, Peter Floderus
Publication date: 30 October 2015
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2015.09.001
Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (7)
A Fast Deterministic Detection of Small Pattern Graphs in Graphs Without Large Cliques ⋮ A fast deterministic detection of small pattern graphs in graphs without large cliques ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The descriptive complexity of subgraph isomorphism without numerics ⋮ Rare siblings speed-up deterministic detection and counting of small pattern graphs ⋮ Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles
Cites Work
- Unnamed Item
- Unnamed Item
- Finding and counting small induced subgraphs efficiently
- On graphs without a \(C_{4}\) or a diamond
- On the complexity of fixed parameter clique and dominating set
- Matrix multiplication via arithmetic progressions
- Paw-free graphs
- Fast rectangular matrix multiplication and applications
- Rectangular matrix multiplication revisited
- On limited nondeterminism and the complexity of the V-C dimension
- Finding and listing induced paths and cycles
- Computing the rooted triplet distance between galled trees by counting triangles
- Counting and Detecting Small Subgraphs via Equations
- Detecting and Counting Small Pattern Graphs
- Induced Subgraph Isomorphism: Are Some Patterns Substantially Easier Than Others?
- Powers of tensors and fast matrix multiplication
- Understanding the Complexity of Induced Subgraph Isomorphisms
- A Linear Recognition Algorithm for Cographs
- Finding a Minimum Circuit in a Graph
- The Parametrized Complexity of Some Fundamental Problems in Coding Theory
- Finding Four-Node Subgraphs in Triangle Time
- Multiplying matrices faster than coppersmith-winograd
This page was built for publication: Induced subgraph isomorphism: are some patterns substantially easier than others?
