Some Problems on Approximate Counting in Graphs and Matroids
From MaRDI portal
Publication:2971623
DOI10.1007/978-3-540-76796-1_23zbMath1359.05128OpenAlexW103249118MaRDI QIDQ2971623
Publication date: 7 April 2017
Published in: Research Trends in Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-76796-1_23
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Cites Work
- Planar graph coloring is not self-reducible, assuming P\(\neq NP\)
- Fast uniform generation of regular graphs
- Inapproximability of the Tutte polynomial
- Random generation of combinatorial structures from a uniform distribution
- Approximate counting, uniform generation and rapidly mixing Markov chains
- Nowhere-zero 6-flows
- Geometric algorithms and combinatorial optimization
- On the problem of approximating the number of bases of a matroid
- Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
- Counting trees in a graph is \(\# \text{P}\)-complete
- Improved bounds for sampling colorings
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- Polynomial-Time Approximation Algorithms for the Ising Model
- Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
- Approximating the Permanent
- The computational complexity of matroid properties
- Combinatorial applications of an inequality from statistical mechanics
- Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
- A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs
- On the computational complexity of the Jones and Tutte polynomials
- A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
