scientific article
From MaRDI portal
Publication:3793731
zbMath0648.68060MaRDI QIDQ3793731
Vijay V. Vazirani, Mihalis Yannakakis
Publication date: 1988
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
computational complexitydirected grapheven cyclesperfect matchingsPfaffian orientations0/1 permanentspolynomial time equivalences
Analysis of algorithms and problem complexity (68Q25) Determinants, permanents, traces, other special matrix functions (15A15) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (5)
Regularity of matrices in min-algebra and its time-complexity ⋮ NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems ⋮ Every 7-regular digraph contains an even cycle ⋮ Matching theory -- a sampler: From Dénes König to the present ⋮ Backdoors to tractable answer set programming
This page was built for publication:
