Finding and counting small induced subgraphs efficiently
From MaRDI portal
Publication:294749
DOI10.1016/S0020-0190(00)00047-8zbMath1339.05394OpenAlexW2150875823WikidataQ56210426 ScholiaQ56210426MaRDI QIDQ294749
Dieter Kratsch, Ton Kloks, 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
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
An \(\mathcal{O}(m\log n)\) algorithm for the weighted stable set problem in claw-free graphs with \(\alpha ({G}) \leq 3\), Counting Subgraphs in Degenerate Graphs, The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics, Two characterisations of minimal triangulations of \(2K_{2}\)-free graphs, Equimatchable claw-free graphs, Exact Weight Subgraphs and the k-Sum Conjecture, Induced subgraph isomorphism: are some patterns substantially easier than others?, Quasipolynomiality of the Smallest Missing Induced Subgraph, Streaming deletion problems Parameterized by vertex cover, Monotone arithmetic complexity of graph homomorphism polynomials, Linear‐time algorithms for eliminating claws in graphs, Computing and listing avoidable vertices and paths, Arboricity, \(h\)-index, and dynamic algorithms, Computing and listing avoidable vertices and paths, On linear algebraic algorithms for the subgraph matching problem and its variants, Finding small complete subgraphs efficiently, On the structure of (pan, even hole)‐free graphs, Are unique subgraphs not easier to find?, A Fast Deterministic Detection of Small Pattern Graphs in Graphs Without Large Cliques, Finding a smallest odd hole in a claw-free graph using global structure, An \(\mathcal{O} (n^2 \log{n})\) algorithm for the weighted stable set problem in claw-free graphs, Weighted well-covered claw-free graphs, A fast deterministic detection of small pattern graphs in graphs without large cliques, On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size, Finding and counting given length cycles, Free fermions behind the disguise, Unnamed Item, About some robustness and complexity properties of \(G\)-graphs networks, Detecting and Counting Small Pattern Graphs, On the complexity of fixed parameter clique and dominating set, Efficient algorithms for clique problems, Intersection graphs of non-crossing paths, Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree, Unnamed Item, Unnamed Item, Counting Subgraphs in Relational Event Graphs, Detecting and enumerating small induced subgraphs in \(c\)-closed graphs, Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments, Detecting directed 4-cycles still faster, Rare siblings speed-up deterministic detection and counting of small pattern graphs, Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition, Time Windowed Data Structures for Graphs, Unique subgraphs are not easier to find, Unnamed Item, Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles
Cites Work
- Unnamed Item
- Finding and counting given length cycles
- Coloring perfect \((K_ 4\)-e)-free graphs
- Paw-free graphs
- On maximal independent sets of vertices in claw-free graphs
- Parallel concepts in graph theory
- Claw-free graphs---a survey
- Arboricity and Subgraph Listing Algorithms
- A Linear Recognition Algorithm for Cographs
- Finding a Minimum Circuit in a Graph
