A fast deterministic detection of small pattern graphs in graphs without large cliques

DOI10.1016/J.TCS.2018.10.028zbMATH Open1421.68137OpenAlexW2898515167WikidataQ129030225 ScholiaQ129030225MaRDI QIDQ1740697FDOQ1740697

Authors: 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

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

zbMATH Keywords

matrix multiplicationtime complexityinduced subgraph isomorphismwitnesses for Boolean matrix product

Mathematics Subject Classification ID

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)

Cites Work

• Powers of tensors and fast matrix multiplication
• Multiplying matrices faster than coppersmith-winograd
• Paw-free graphs
• Counting and detecting small subgraphs via equations
• Finding and counting small induced subgraphs efficiently
• Title not available (Why is that?)
• A Linear Recognition Algorithm for Cographs
• Finding a Minimum Circuit in a Graph
• An improved combinatorial algorithm for Boolean matrix multiplication
• On graphs without a \(C_{4}\) or a diamond
• On the complexity of fixed parameter clique and dominating set
• A survey of bounds for classical Ramsey numbers
• Experimental and Efficient Algorithms
• Finding Four-Node Subgraphs in Triangle Time
• Faster multi-witnesses for Boolean matrix multiplication
• Finding and listing induced paths and cycles
• Induced subgraph isomorphism: are some patterns substantially easier than others?
• Detecting and Counting Small Pattern Graphs

Cited In (3)

• Rare siblings speed-up deterministic detection and counting of small pattern graphs
• 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)