NC algorithms for computing the number of perfect matchings in K₃,3-free graphs and related problems
From MaRDI portal
Publication:1120597
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)
Cites work
- A note on primitive skew curves
- An approach to the subgraph homeomorphism problem
- Bemerkungen zu Hadwigers Vermutung
- Constructing a perfect matching is in random NC
- Dividing a Graph into Triconnected Components
- Fast Parallel Matrix Inversion Algorithms
- scientific article; zbMATH DE number 3965444 (Why is no real title available?)
- scientific article; zbMATH DE number 3965452 (Why is no real title available?)
- scientific article; zbMATH DE number 4058868 (Why is no real title available?)
- scientific article; zbMATH DE number 4090822 (Why is no real title available?)
- scientific article; zbMATH DE number 3517179 (Why is no real title available?)
- scientific article; zbMATH DE number 3236772 (Why is no real title available?)
- scientific article; zbMATH DE number 3326387 (Why is no real title available?)
- Matching is as easy as matrix inversion
- Matching theory
- Parallel Algorithms in Graph Theory: Planarity Testing
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- The complexity of computing the permanent
- The Factorization of Linear Graphs
- The NP-completeness column: An ongoing guide
Cited in
(34)- Matching theory -- a sampler: From Dénes König to the present
- A parallel algorithm for finding a triconnected component separator with an application
- On the permanent of certain (0,1) Toeplitz matrices
- Tight upper bound on the number of edges in a bipartite \(K_{3,3}\)-free or \(K_{5}\)-free graph with an application.
- The combinatorial approach yields an NC algorithm for computing Pfaffians
- Random parallel algorithms for finding exact branchings, perfect matchings, and cycles
- Pfaffian pairs and parities: counting on linear matroid intersection and parity problems
- Almost exact matchings
- Pfaffian orientations and perfect matchings of scale-free networks
- An NC algorithm for the perfect matching problem in larger cycle-free graphs
- Some tractable win-lose games
- Almost Exact Matchings
- scientific article; zbMATH DE number 3965452 (Why is no real title available?)
- scientific article; zbMATH DE number 4062621 (Why is no real title available?)
- scientific article; zbMATH DE number 4064510 (Why is no real title available?)
- Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases
- NC algorithms for computing a perfect matching and a maximum flow in one-crossing-minor-free graphs
- Bipartite perfect matching is in quasi-NC
- NC algorithms for weighted planar perfect matching and related problems
- Counting problems in parameterized complexity
- Counting the number of perfect matchings in \(K_{5}\)-free graphs
- Counting shortest two disjoint paths in cubic planar graphs with an NC algorithm
- Parallel algorithms for matroid intersection and matroid parity
- Extending planar graph algorithms to \(K_{3,3}\)-free graphs
- Tractable minor-free generalization of planar zero-field Ising models
- Pfaffian pairs and parities: counting on linear matroid intersection and parity problems
- Compression with wildcards: all exact or all minimal hitting sets
- Reconfiguring planar perfect matchings via bounded length alternating cycles
- Packing dimers to maximum occupancy under soft-core constraints
- On the exact matching problem in dense graphs
- Killing a vortex
- The Even-Path problem in directed single-crossing-minor-free graphs
- Coloring algorithms for \(K_ 5\)-minor free graphs
- Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
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)
