Approximating the permanent of graphs with large factors

DOI10.1016/0304-3975(92)90234-7zbMath0766.68056OpenAlexW2044105411MaRDI QIDQ1199692

Paul Dagum, Michael Luby

Publication date: 16 January 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(92)90234-7

zbMATH Keywords

bipartite graphscounting problemperfect matchingspermanent of graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Determinants, permanents, traces, other special matrix functions (15A15) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Block interpolation: a framework for tight exponential-time counting complexity ⋮ On the number of Eulerian orientations of a graph ⋮ Holographic reduction, interpolation and hardness ⋮ On the expansion of combinatorial polytopes ⋮ The complexity of generalized domino tilings ⋮ On the Number of α-Orientations ⋮ Unnamed Item ⋮ Counting Minimal Dominating Sets ⋮ Rank-maximal matchings -- structure and algorithms ⋮ Computational complexity of three-dimensional discrete tomography with missing data ⋮ Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width ⋮ An update on Minc's survey of open problems involving permanents ⋮ Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value ⋮ Bipartite 3-regular counting problems with mixed signs ⋮ Bipartite 3-regular counting problems with mixed signs ⋮ Spanning tree constrained determinantal point processes are hard to (approximately) evaluate ⋮ Counting Perfect Matchings and the Switch Chain ⋮ Counting edge-injective homomorphisms and matchings on restricted graph classes ⋮ A load balancing strategy for parallel computation of sparse permanents

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Random generation of combinatorial structures from a uniform distribution
• Matching theory
• Eigenvalues and expanders
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
• Perfect matching for regular graphs is \(AC^ 0\)-hard for the general matching problem
• On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated Annealing
• Improved Time Bounds for the Maximum Flow Problem
• Monte-Carlo approximation algorithms for enumeration problems
• A Monte-Carlo Algorithm for Estimating the Permanent