Parameterized counting of trees, forests and matroid bases
From MaRDI portal
Publication:2399367
DOI10.1007/978-3-319-58747-9_10zbMath1489.68175arXiv1611.01823OpenAlexW2553008661MaRDI QIDQ2399367
Publication date: 22 August 2017
Full work available at URL: https://arxiv.org/abs/1611.01823
Trees (05C05) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Combinatorial aspects of matroids and geometric lattices (05B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (5)
Compactors for parameterized counting problems ⋮ Parameterised counting in logspace ⋮ Parameterized Counting and Cayley Graph Expanders ⋮ Unnamed Item ⋮ Parameterized counting of partially injective homomorphisms
Cites Work
- Unnamed Item
- A parameterized view on matroid optimization problems
- Counting trees in a graph is \(\# \text{P}\)-complete
- Bicycle dimension and special points of the Tutte polynomial
- Counting bases of representable matroids
- Deterministic Truncation of Linear Matroids
- FAST EXPONENTIAL-TIME ALGORITHMS FOR THE FOREST COUNTING AND THE TUTTE POLYNOMIAL COMPUTATION IN GRAPH CLASSES
- Matrix Generalizations of Some Theorems on Trees, Cycles and Cocycles in Graphs
- The Computational Complexity of the Tutte Plane: the Bipartite Case
- Subgraph Isomorphism in Planar Graphs and Related Problems
- Fine-grained dichotomies for the Tutte plane and Boolean #CSP
- Counting Matchings of Size k Is $\sharp$ W[1-Hard]
- Parameterized Algorithms
This page was built for publication: Parameterized counting of trees, forests and matroid bases
