scientific article; zbMATH DE number 4064510

MaRDI QIDQ3798259zbMATH OpenFDO

Authors Joseph (Seffi) Naor

Publication date 1988

zbMATH Keywords

line graphNCperfect matching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• An NC algorithm for the perfect matching problem in larger cycle-free graphs
• Planar graph perfect matching is in NC
• scientific article; zbMATH DE number 4062621
• NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
• Some perfect matchings and perfect half-integral matchings in NC

Cited in

(4)

• On perfect matchings of complements of line graphs
• scientific article; zbMATH DE number 1455340 (Why is no real title available?)
• Graphs with second smallest number of perfect matchings of line graphs.
• Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3798259)