Counting subgraphs in somewhere dense graphs
From MaRDI portal
Enumeration in graph theory (05C30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)
Cites work
- A fixed-parameter perspective on \#BIS
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- Can you beat treewidth?
- Color-coding
- Counting \(H-\)colorings of partial \(k-\)trees
- Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory
- Counting edge-injective homomorphisms and matchings on restricted graph classes
- Counting induced subgraphs: an algebraic approach to \#W[1]-hardness
- Counting matchings of size \(k\) is \#W[1]-hard
- Counting Small Induced Subgraphs Satisfying Monotone Properties
- Counting small induced subgraphs with hereditary properties
- Counting Subgraphs in Degenerate Graphs
- Counting subgraphs in somewhere dense graphs
- First-order logic and twin-width in tournaments
- FO model checking of interval graphs
- Graph minors. V. Excluding a planar graph
- Graph theory
- 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 7650386 (Why is no real title available?)
- scientific article; zbMATH DE number 7788476 (Why is no real title available?)
- Interpreting nowhere dense graph classes as a classical notion of model theory
- Large networks and graph limits
- On nowhere dense graphs
- On the complexity of k-SAT
- On the presence of disjoint subgraphs of a specified type
- On tree width, bramble size, and expansion
- Parameterized algorithms
- Parameterized Counting and Cayley Graph Expanders
- Parameterizing the permanent: hardness for fixed excluded minors
- Parametrized complexity theory.
- Sparsity. Graphs, structures, and algorithms
- Strong computational lower bounds via parameterized complexity
- Testing first-order properties for subclasses of sparse graphs
- The challenges of unbounded treewidth in parameterised subgraph counting problems
- The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
- The complexity of counting homomorphisms seen from the other side
- The Complexity of Enumeration and Reliability Problems
- The parameterised complexity of counting connected subgraphs and graph motifs
- The Parameterized Complexity of Counting Problems
- Tight lower bounds for certain parameterized NP-hard problems
- Tractable hypergraph properties for constraint satisfaction and conjunctive queries
- Twin-width. I: Tractable FO model checking
- Understanding the Complexity of Induced Subgraph Isomorphisms
This page was built for publication: Counting subgraphs in somewhere dense graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6621747)
