Reachability and Matching in Single Crossing Minor Free Graphs

Samir Datta, Chetan Gupta, Rahul Jain, Anish Mukherjee, Vimalraj Sharma, Raghunath Tewari

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference article in proceedingsScientificvertaisarvioitu

35 Lataukset (Pure)

Abstrakti

We show that for each single crossing graph H, a polynomially bounded weight function for all H-minor free graphs G can be constructed in logspace such that it gives nonzero weights to all the cycles in G. This class of graphs subsumes almost all classes of graphs for which such a weight function is known to be constructed in logspace. As a consequence, we obtain that for the class of H-minor free graphs where H is a single crossing graph, reachability can be solved in UL, and bipartite maximum matching can be solved in SPL, which are small subclasses of the parallel complexity class NC. In the restrictive case of bipartite graphs, our maximum matching result improves upon the recent result of Eppstein and Vazirani (SIAM J. Computing 2021), where they show an NC bound for constructing perfect matching in general single crossing minor free graphs.
AlkuperäiskieliEnglanti
Otsikko41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
AlaotsikkoFSTTCS 2021, December 15–17, 2021, Virtual Conference
KustantajaSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Sivut1-16
Sivumäärä16
ISBN (elektroninen)978-3-95977-215-0
TilaJulkaistu - 29 marrask. 2021
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaIARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science - Virtual, Online
Kesto: 15 jouluk. 202117 jouluk. 2021
Konferenssinumero: 41

Julkaisusarja

NimiLeibniz International Proceedings in Informatics (LIPIcs)
KustantajaSchloss Dagstuhl –Leibniz Center for Informatics
Vuosikerta213
ISSN (elektroninen)1868-8969

Conference

ConferenceIARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
LyhennettäFSTTCS
KaupunkiVirtual, Online
Ajanjakso15/12/202117/12/2021

Sormenjälki

Sukella tutkimusaiheisiin 'Reachability and Matching in Single Crossing Minor Free Graphs'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä