Finding and counting small induced subgraphs efficiently
From MaRDI portal
Publication:294749
DOI10.1016/S0020-0190(00)00047-8zbMATH Open1339.05394OpenAlexW2150875823WikidataQ56210426 ScholiaQ56210426MaRDI QIDQ294749FDOQ294749
Authors: Ton Kloks, Dieter Kratsch, Haiko Müller 
Publication date: 16 June 2016
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019000000478?np=y
Recommendations
- Finding small complete subgraphs efficiently
- Detecting and enumerating small induced subgraphs in \(c\)-closed graphs
- Counting Small Induced Subgraphs Satisfying Monotone Properties
- Efficient enumeration of subgraphs and induced subgraphs with bounded girth
- Finding induced subgraphs via minimal triangulations
- Counting and detecting small subgraphs via equations and matrix multiplication
- Counting and detecting small subgraphs via equations
- Faster Subgraph Counting in Sparse Graphs
- Faster algorithms for finding and counting subgraphs
- Counting small induced subgraphs with hereditary properties
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)
Cites Work
- Claw-free graphs---a survey
- Finding and counting given length cycles
- On maximal independent sets of vertices in claw-free graphs
- Parallel concepts in graph theory
- Coloring perfect \((K_ 4\)-e)-free graphs
- Paw-free graphs
- Title not available (Why is that?)
- Arboricity and Subgraph Listing Algorithms
- A Linear Recognition Algorithm for Cographs
- Finding a Minimum Circuit in a Graph
Cited In (53)
- Finding and counting small tournaments in large tournaments
- Arboricity and Subgraph Listing Algorithms
- Title not available (Why is that?)
- Two characterisations of minimal triangulations of \(2K_{2}\)-free graphs
- An \(\mathcal{O}(m\log n)\) algorithm for the weighted stable set problem in claw-free graphs with \(\alpha ({G}) \leq 3\)
- On graphs without a \(C_{4}\) or a diamond
- A fast deterministic detection of small pattern graphs in graphs without large cliques
- Finding and counting given length cycles
- Efficient algorithms for clique problems
- Detecting and counting small pattern graphs
- Unique subgraphs are not easier to find
- On the complexity of fixed parameter clique and dominating set
- Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments
- Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
- Finding a smallest odd hole in a claw-free graph using global structure
- Finding four-node subgraphs in triangle time
- Quasipolynomiality of the Smallest Missing Induced Subgraph
- About some robustness and complexity properties of \(G\)-graphs networks
- Tensor network complexity of multilinear maps
- An \(\mathcal{O} (n^2 \log{n})\) algorithm for the weighted stable set problem in claw-free graphs
- Time windowed data structures for graphs
- Computing and listing avoidable vertices and paths
- Graph pattern detection: hardness for all induced patterns and faster noninduced cycles
- Arboricity, \(h\)-index, and dynamic algorithms
- Counting connected subgraphs with maximum-degree-aware sieving
- Rare siblings speed-up deterministic detection and counting of small pattern graphs
- Finding small complete subgraphs efficiently
- Induced subgraph isomorphism: are some patterns substantially easier than others?
- Intersection graphs of non-crossing paths
- Equimatchable claw-free graphs
- Monotone arithmetic complexity of graph homomorphism polynomials
- Linear‐time algorithms for eliminating claws in graphs
- Detecting directed 4-cycles still faster
- Counting and detecting small subgraphs via equations and matrix multiplication
- Weighted well-covered claw-free graphs
- On linear algebraic algorithms for the subgraph matching problem and its variants
- A fast deterministic detection of small pattern graphs in graphs without large cliques
- Detecting and enumerating small induced subgraphs in \(c\)-closed graphs
- Finding and listing induced paths and cycles
- Exact weight subgraphs and the \(k\)-sum conjecture
- Computing and listing avoidable vertices and paths
- The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics
- Finding and counting small induced subgraphs efficiently
- On the structure of (pan, even hole)-free graphs
- On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
- Free fermions behind the disguise
- Counting Subgraphs in Degenerate Graphs
- Counting subgraphs in relational event graphs
- Counting and detecting small subgraphs via equations
- Are unique subgraphs not easier to find?
- On the first-order complexity of induced subgraph isomorphism
- Streaming deletion problems Parameterized by vertex cover
- Solving the weighted stable set problem in claw-free graphs via decomposition
This page was built for publication: Finding and counting small induced subgraphs efficiently
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q294749)
