English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

I t has been known for a long t ime now tha t the problem of counting the number of perfect matchings in a planar graph is in NC. This result is based on the notion of a pfaffian orientation of a graph. (Recently, Galluccio and Loebl [7] gave a P-t ime algorithm for the case of graphs of small genus.) However, it is not known if the corresponding search problem, tha t of finding one perfect matching in a planar graph, is in NC. This situation is intriguing as it seems to contradict our intuit ion tha t search should be easier than counting. For the case of planar bipartite graphs, Miller and Naor [22] showed tha t a perfect matching can indeed be found using an NC algorithm. We present a very different NG-algorithm for this problem. Unlike the Miller-Naor algorithm, our approach directly uses the fact tha t counting is in NC, and it also generalizes to the problem of finding a perfect matching in a bipar t i te graph of small (O(log n)) genus. I t also rekindles the hope for an NC-algorithm to find a perfect matching in a non-bipart i te planar graph. Along the way, we modify the algorithm of Gallucio and Loebl [7] to show that counting the number of perfect matchings in graphs of small genus is in NC.

A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract)