Faster algorithms for counting subgraphs in sparse graphs
type: Item
instance of: scholarly article
title: Faster algorithms for counting subgraphs in sparse graphs
author: Marco Bressan
published in: Algorithmica
publication date: 2021-07-26T00:00:00Z
full work available at URL: https://arxiv.org/abs/1805.02089
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 05Cxx
zbMATH DE Number: 7374884
zbMATH Keywords: subgraph counting
zbMATH Keywords: tree decomposition
zbMATH Keywords: degeneracy
zbMATH Keywords: sparsity
MaRDI profile type: Publication
OpenAlex ID: W3132242427
cites work: Q3003675
cites work: Q3424888
cites work: Faster Subgraph Counting in Sparse Graphs
cites work: Tight lower bounds for certain parameterized NP-hard problems
cites work: Strong computational lower bounds via parameterized complexity
cites work: Arboricity and Subgraph Listing Algorithms
cites work: Homomorphisms are a good basis for counting small subgraphs
cites work: Graph Theory
cites work: Arboricity and bipartite subgraph listing algorithms
cites work: Subgraph Isomorphism in Planar Graphs and Related Problems
cites work: Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time
cites work: Listing All Maximal Cliques in Large Sparse Real-World Graphs
cites work: Exact exponential algorithms.
cites work: Are there any good digraph width measures?
cites work: Q2963895
cites work: On tree width, bramble size, and expansion
cites work: Which problems have strongly exponential complexity?
cites work: Graph-Theoretic Concepts in Computer Science
cites work: Powers of tensors and fast matrix multiplication
cites work: A note on the graph isomorphism counting problem
cites work: Sparsity. Graphs, structures, and algorithms
cites work: On nowhere dense graphs
cites work: Q3688439
cites work: Computing the number of induced copies of a fixed graph in a bounded degree graph
DOI: 10.1007/S00453-021-00811-0
description: scientific article; zbMATH DE number 7374884