The complexity of pattern counting in directed graphs, parameterised by the outdegree
From MaRDI portal
Publication:6499249
DOI10.1145/3564246.3585204MaRDI QIDQ6499249FDOQ6499249
Authors: Marco Bressan, Matthias Lanzinger, Marc Roth 
Publication date: 8 May 2024
parameterized complexitysubgraph countinggraph motifspattern countingdirected graph countinginduced subgraph counting
Cites Work
- Statistical mechanics of complex networks
- Large networks and graph limits
- Title not available (Why is that?)
- Parametrized complexity theory.
- Can you beat treewidth?
- Approximate Counting of k -Paths: Simpler, Deterministic, and in Polynomial Space
- On the complexity of \(k\)-SAT
- Structural tractability of counting of solutions to conjunctive queries
- Extensor-coding
- Arboricity and Subgraph Listing Algorithms
- Strong computational lower bounds via parameterized complexity
- Tight lower bounds for certain parameterized NP-hard problems
- Rooted grid minors
- Tractable hypergraph properties for constraint satisfaction and conjunctive queries
- Understanding the Complexity of Induced Subgraph Isomorphisms
- The Parameterized Complexity of Counting Problems
- The parameterised complexity of counting connected subgraphs and graph motifs
- Title not available (Why is that?)
- Counting Subgraphs in Degenerate Graphs
- Homomorphisms are a good basis for counting small subgraphs
- The challenges of unbounded treewidth in parameterised subgraph counting problems
- Counting matchings of size \(k\) is \#W[1]-hard
- Exponential Time Complexity of the Permanent and the Tutte Polynomial
- Faster algorithms for counting subgraphs in sparse graphs
- Counting Homomorphic Cycles in Degenerate Graphs
- When is approximate counting for conjunctive queries tractable?
- Counting Answers to Existential Questions
- Title not available (Why is that?)
- Title not available (Why is that?)
This page was built for publication: The complexity of pattern counting in directed graphs, parameterised by the outdegree
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499249)
