Induced subgraph isomorphism: are some patterns substantially easier than others?

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

zbMATH Keywords

time complexitycounting subgraphsinduced subgraph isomorphismdetecting subgraphs

Mathematics Subject Classification ID

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?