The combinatorial approach yields an NC algorithm for computing Pfaffians

DOI10.1016/j.dam.2003.12.001zbMath1053.05081OpenAlexW2088698934MaRDI QIDQ1887034

P. R. Subramanya, V. Vinay, Meena Mahajan

Publication date: 23 November 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://eprints.iisc.ac.in/2860/1/A36pfaff.pdf

zbMATH Keywords

MatchingAlgorithmCombinatoricsPfaffianNC

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

The Faddeev-LeVerrier algorithm and the Pfaffian ⋮ General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems ⋮ On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices ⋮ Counting the number of perfect matchings in \(K_{5}\)-free graphs ⋮ Computing girth and cogirth in perturbed graphic matroids ⋮ Planar Maximum Matching: Towards a Parallel Algorithm

Cites Work

• The complexity of computing the permanent
• Matching theory
• Matching is as easy as matrix inversion
• NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
• On the theory of Pfaffian orientations. II: \(T\)-joins, \(k\)-cuts, and duality of enumeration
• On the computation of pfaffians
• Planarity testing in parallel
• Overlapping Pfaffians
• Isolation, matching, and counting uniform and nonuniform upper bounds
• A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract)
• Random pseudo-polynomial algorithms for exact matroid problems
• Flow in Planar Graphs with Multiple Sources and Sinks
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The combinatorial approach yields an NC algorithm for computing Pfaffians