Parameterized counting of trees, forests and matroid bases

DOI10.1007/978-3-319-58747-9_10zbMath1489.68175arXiv1611.01823OpenAlexW2553008661MaRDI QIDQ2399367

Cornelius Brand, Marc Roth

Publication date: 22 August 2017

Full work available at URL: https://arxiv.org/abs/1611.01823

Mathematics Subject Classification ID

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