NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
From MaRDI portal
Publication:1120597
DOI10.1016/0890-5401(89)90017-5zbMath0673.05075OpenAlexW2022124805MaRDI QIDQ1120597
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
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
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
