Graph pattern detection: hardness for all induced patterns and faster noninduced cycles
From MaRDI portal
Complexity of computation (including implicit computational complexity) (03D15) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Pattern recognition, speech recognition (68T10)
Recommendations
- Graph pattern detection: hardness for all induced patterns and faster non-induced cycles
- 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
- Induced subgraph isomorphism: are some patterns substantially easier than others?
- Detecting and counting small pattern graphs
Cites work
- A fast deterministic detection of small pattern graphs in graphs without large cliques
- A Linear Recognition Algorithm for Cographs
- A simple linear-time algorithm for computing the center of an interval graph
- Any 7-chromatic graph has \(K_7\) or \(K_{4,4}\) as a minor
- Can you beat treewidth?
- Clique-based lower bounds for parsing tree-adjoining grammars
- Color-coding
- Counting and detecting small subgraphs via equations
- Cycles of even length in graphs
- Detecting and Counting Small Pattern Graphs
- Detecting short directed cycles using rectangular matrix multiplication and dynamic programming
- Efficient algorithms for clique problems
- Faster algorithms for finding and counting subgraphs
- Finding a Minimum Circuit in a Graph
- Finding and counting given length cycles
- Finding and counting small induced subgraphs efficiently
- Finding even cycles even faster
- Finding even cycles faster via capped k-walks
- Finding four-node subgraphs in triangle time
- Finding, minimizing, and counting weighted subgraphs
- Hadwiger's conjecture for \(K_ 6\)-free graphs
- Hadwiger's conjecture is true for almost every graph
- Homomorphisms are a good basis for counting small subgraphs
- scientific article; zbMATH DE number 3910446 (Why is no real title available?)
- scientific article; zbMATH DE number 3974318 (Why is no real title available?)
- scientific article; zbMATH DE number 5485586 (Why is no real title available?)
- If the current clique algorithms are optimal, so is Valiant's parser
- Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor
- Induced subgraph isomorphism: are some patterns substantially easier than others?
- Multiplying matrices faster than coppersmith-winograd
- On the complexity of k-SAT
- On the complexity of fixed parameter clique and dominating set
- On the interval containing at least one prime number
- On the primes in the interval \([3n,4n]\)
- Powers of tensors and fast matrix multiplication
- The chromatic number of random graphs
- The four-colour theorem
- Tight hardness for shortest cycles and paths in sparse graphs
- Tight lower bounds for certain parameterized NP-hard problems
- Über eine Eigenschaft der ebenen Komplexe
Cited in
(9)- A fast deterministic detection of small pattern graphs in graphs without large cliques
- Induced subgraph isomorphism: are some patterns substantially easier than others?
- A fast deterministic detection of small pattern graphs in graphs without large cliques
- Graph pattern detection: hardness for all induced patterns and faster non-induced cycles
- Streaming deletion problems Parameterized by vertex cover
- Fast approximate counting of cycles
- Coverability in VASS revisited: improving Rackoff's bounds to obtain conditional optimality
- Fine-grained classification of detecting dominating patterns
- Induced subgraph isomorphism: are some patterns substantially easier than others?
This page was built for publication: Graph pattern detection: hardness for all induced patterns and faster noninduced cycles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5860479)
