A Fast Deterministic Detection of Small Pattern Graphs in Graphs Without Large Cliques
DOI10.1007/978-3-319-53925-6_17zbMath1464.68290OpenAlexW2588721740MaRDI QIDQ2980911
Mirosław Kowaluk, Andrzej Lingas
Publication date: 5 May 2017
Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-53925-6_17
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 (2)
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
- Induced subgraph isomorphism: are some patterns substantially easier than others?
- Faster multi-witnesses for Boolean matrix multiplication
- Paw-free graphs
- 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
