Approximating the permanent of graphs with large factors
DOI10.1016/0304-3975(92)90234-7zbMATH Open0766.68056OpenAlexW2044105411MaRDI QIDQ1199692FDOQ1199692
Authors: 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
Recommendations
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Determinants, permanents, traces, other special matrix functions (15A15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Eigenvalues and expanders
- Title not available (Why is that?)
- Matching theory
- Title not available (Why is that?)
- The complexity of computing the permanent
- Random generation of combinatorial structures from a uniform distribution
- Title not available (Why is that?)
- Approximate counting, uniform generation and rapidly mixing Markov chains
- A Monte-Carlo Algorithm for Estimating the Permanent
- Monte-Carlo approximation algorithms for enumeration problems
- Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
- On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated Annealing
- Improved Time Bounds for the Maximum Flow Problem
- Perfect matching for regular graphs is \(AC^ 0\)-hard for the general matching problem
Cited In (22)
- Counting edge-injective homomorphisms and matchings on restricted graph classes
- On the Number of α-Orientations
- Counting perfect matchings and the switch chain
- Computational complexity of three-dimensional discrete tomography with missing data
- Counting problems in parameterized complexity
- A polynomial-time approximation algorithm for the number of \(k\)-matchings in bipartite graphs
- On the expansion of combinatorial polytopes
- On the number of Eulerian orientations of a graph
- Computational complexity of counting coincidences
- Faster exponential-time algorithms in graphs of bounded average degree
- The complexity of generalized domino tilings
- 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
- Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value
- Approximating permanents and hafnians
- Holographic reduction, interpolation and hardness
- Counting weighted independent sets beyond the permanent
- 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
- A load balancing strategy for parallel computation of sparse permanents.
- Counting minimal dominating sets
This page was built for publication: Approximating the permanent of graphs with large factors
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1199692)
