NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems

DOI10.1016/0890-5401(89)90017-5zbMath0673.05075OpenAlexW2022124805MaRDI QIDQ1120597

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

zbMATH Keywords

computing the number of perfect matchings

Mathematics Subject Classification ID

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)

Related Items (24)

A parallel algorithm for finding a triconnected component separator with an application ⋮ The combinatorial approach yields an NC algorithm for computing Pfaffians ⋮ Random parallel algorithms for finding exact branchings, perfect matchings, and cycles ⋮ On the permanent of certain \((0,1)\) Toeplitz matrices ⋮ NC Algorithms for Weighted Planar Perfect Matching and Related Problems ⋮ Compression with wildcards: all exact or all minimal hitting sets ⋮ Almost exact matchings ⋮ Unnamed Item ⋮ Coloring algorithms for \(K_ 5\)-minor free graphs ⋮ Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs ⋮ Counting the number of perfect matchings in \(K_{5}\)-free graphs ⋮ Some Tractable Win-Lose Games ⋮ Matching theory -- a sampler: From Dénes König to the present ⋮ Unnamed Item ⋮ Extending planar graph algorithms to \(K_{3,3}\)-free graphs ⋮ Pfaffian orientations and perfect matchings of scale-free networks ⋮ Pfaffian pairs and parities: counting on linear matroid intersection and parity problems ⋮ NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs ⋮ Bipartite Perfect Matching is in Quasi-NC ⋮ Tractable minor-free generalization of planar zero-field Ising models ⋮ Tight upper bound on the number of edges in a bipartite \(K_{3,3}\)-free or \(K_{5}\)-free graph with an application. ⋮ Parallel algorithms for matroid intersection and matroid parity ⋮ Pfaffian Pairs and Parities: Counting on Linear Matroid Intersection and Parity Problems ⋮ Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Bemerkungen zu Hadwigers Vermutung
• An approach to the subgraph homeomorphism problem
• Matching theory
• Matching is as easy as matrix inversion
• Constructing a perfect matching is in random NC
• Parallel computation for well-endowed rings and space-bounded probabilistic machines
• Parallel Algorithms in Graph Theory: Planarity Testing
• Fast Parallel Matrix Inversion Algorithms
• Dividing a Graph into Triconnected Components
• The Factorization of Linear Graphs
• A note on primitive skew curves
• The NP-completeness column: An ongoing guide

This page was built for publication: NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems