NC algorithms for computing the number of perfect matchings in K₃,3-free graphs and related problems
DOI10.1016/0890-5401(89)90017-5zbMATH Open0673.05075OpenAlexW2022124805MaRDI QIDQ1120597FDOQ1120597
Authors: Vijay V. Vazirani 
Publication date: 1989
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0890-5401(89)90017-5
Recommendations
- scientific article; zbMATH DE number 4062621
- An NC algorithm for the perfect matching problem in larger cycle-free graphs
- Some perfect matchings and perfect half-integral matchings in NC
- NC algorithms for computing a perfect matching and a maximum flow in one-crossing-minor-free graphs
- A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Matching theory
- Title not available (Why is that?)
- Title not available (Why is that?)
- The Factorization of Linear Graphs
- The complexity of computing the permanent
- Constructing a perfect matching is in random NC
- Matching is as easy as matrix inversion
- Dividing a Graph into Triconnected Components
- Title not available (Why is that?)
- Fast Parallel Matrix Inversion Algorithms
- Title not available (Why is that?)
- A note on primitive skew curves
- Bemerkungen zu Hadwigers Vermutung
- The NP-completeness column: An ongoing guide
- An approach to the subgraph homeomorphism problem
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- Parallel Algorithms in Graph Theory: Planarity Testing
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (29)
- Tight upper bound on the number of edges in a bipartite \(K_{3,3}\)-free or \(K_{5}\)-free graph with an application.
- Almost Exact Matchings
- An NC algorithm for the perfect matching problem in larger cycle-free graphs
- Tractable minor-free generalization of planar zero-field Ising models
- Counting problems in parameterized complexity
- Title not available (Why is that?)
- On the permanent of certain \((0,1)\) Toeplitz matrices
- NC algorithms for computing a perfect matching and a maximum flow in one-crossing-minor-free graphs
- Extending planar graph algorithms to \(K_{3,3}\)-free graphs
- Some tractable win-lose games
- Bipartite perfect matching is in quasi-NC
- Matching theory -- a sampler: From Dénes König to the present
- Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases
- Almost exact matchings
- Pfaffian pairs and parities: counting on linear matroid intersection and parity problems
- The combinatorial approach yields an NC algorithm for computing Pfaffians
- Compression with wildcards: all exact or all minimal hitting sets
- Parallel algorithms for matroid intersection and matroid parity
- NC algorithms for weighted planar perfect matching and related problems
- Pfaffian pairs and parities: counting on linear matroid intersection and parity problems
- Title not available (Why is that?)
- Coloring algorithms for \(K_ 5\)-minor free graphs
- A parallel algorithm for finding a triconnected component separator with an application
- Random parallel algorithms for finding exact branchings, perfect matchings, and cycles
- Counting the number of perfect matchings in \(K_{5}\)-free graphs
- Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
- Title not available (Why is that?)
- Pfaffian orientations and perfect matchings of scale-free networks
- Title not available (Why is that?)
This page was built for publication: NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1120597)
