Vi presenterar en randomiserad algoritm för att hitta maximal matchningar i planar grafer i tid O(n'~ där co är exponenten för den mest kända matris multiplikation algoritm. Eftersom co < 2.38 bryter denna algoritm igenom O (n J.5)-barriären för det matchande problemet. Detta är det första resultatet av denna typ av allmänna planar grafer. Vi presenterar också en algoritm lor som genererar perfekta matchningar i plana grafer jämnt slumpmässigt med hjälp av O (n ~ aritmetiska operationer. Våra algoritmer är baserade på Gaussian eliminering strategi för maximal matchningar infördes i [ 16].
Detta gjorde det möjligt för Mucha och Sankowski REF att hitta maximala matchningar via Gaussian eliminering i plana grafer i O (n) /2 ) tid, där  på < 2,38 är exponenten för den mest kända matris multiplikation algoritm.
Maximum matchings in planar graphs via gaussian elimination
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}