A fast deterministic detection of small pattern graphs in graphs without large cliques
DOI10.1016/j.tcs.2018.10.028zbMath1421.68137OpenAlexW2898515167MaRDI QIDQ1740697
Mirosław Kowaluk, Andrzej Lingas
Publication date: 2 May 2019
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2018.10.028
time complexitymatrix multiplicationinduced subgraph isomorphismwitnesses for Boolean matrix product
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (1)
Cites Work
- 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
- Induced subgraph isomorphism: are some patterns substantially easier than others?
- Faster multi-witnesses for Boolean matrix multiplication
- Paw-free graphs
- An improved combinatorial algorithm for Boolean matrix multiplication
- Finding and listing induced paths and cycles
- Counting and Detecting Small Subgraphs via Equations
- Powers of tensors and fast matrix multiplication
- A Linear Recognition Algorithm for Cographs
- Finding a Minimum Circuit in a Graph
- A survey of bounds for classical Ramsey numbers
- Finding Four-Node Subgraphs in Triangle Time
- Multiplying matrices faster than coppersmith-winograd
- Detecting and Counting Small Pattern Graphs
- Experimental and Efficient Algorithms
This page was built for publication: A fast deterministic detection of small pattern graphs in graphs without large cliques
