A fast deterministic detection of small pattern graphs in graphs without large cliques
DOI10.1016/J.TCS.2018.10.028zbMATH Open1421.68137OpenAlexW2898515167WikidataQ129030225 ScholiaQ129030225MaRDI QIDQ1740697FDOQ1740697
matrix multiplicationtime complexityinduced subgraph isomorphismwitnesses for Boolean matrix product
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Recommendations
- A fast deterministic detection of small pattern graphs in graphs without large cliques
- Detecting and counting small pattern graphs
- Detecting and Counting Small Pattern Graphs
- Graph pattern detection: hardness for all induced patterns and faster non-induced cycles
- Graph pattern detection: hardness for all induced patterns and faster noninduced cycles
Cites Work
- scientific article; zbMATH DE number 3910446 (Why is no real title available?)
- A Linear Recognition Algorithm for Cographs
- A survey of bounds for classical Ramsey numbers
- Counting and detecting small subgraphs via equations
- Detecting and counting small pattern graphs
- Experimental and Efficient Algorithms
- Faster multi-witnesses for Boolean matrix multiplication
- Finding a Minimum Circuit in a Graph
- Finding and counting small induced subgraphs efficiently
- Finding and listing induced paths and cycles
- Finding four-node subgraphs in triangle time
- Induced subgraph isomorphism: are some patterns substantially easier than others?
- Multiplying matrices faster than coppersmith-winograd
- On graphs without a \(C_{4}\) or a diamond
- On the complexity of fixed parameter clique and dominating set
- Paw-free graphs
- Powers of tensors and fast matrix multiplication
Cited In (6)
- Graph pattern detection: hardness for all induced patterns and faster non-induced cycles
- Graph pattern detection: hardness for all induced patterns and faster noninduced cycles
- Rare siblings speed-up deterministic detection and counting of small pattern graphs
- A fast deterministic detection of small pattern graphs in graphs without large cliques
- Detecting and enumerating small induced subgraphs in \(c\)-closed graphs
- Detecting and Counting Small Pattern Graphs
This page was built for publication: A fast deterministic detection of small pattern graphs in graphs without large cliques
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1740697)
