Fast Distributed MIS and Maximal Matching on Spatial and PLB-Bounded Scale-Free Networks: A Single-Event Meta-Theorem with Geometry and PLB-U/L/N

We prove an axiomatic meta-theorem yielding O(log log n)-round randomized algorithms for maximal independent set (MIS) and maximal matching on broad classes of scale-free networks. Our framework unifies two flavors: (i) geometry-driven rank-1 models (

Authors

Institutions

Publication Details

Published
2025-10-14
DOI
https://doi.org/10.36227/techrxiv.176045769.91474608/v1
Primary Topic
Distributed systems and fault tolerance
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Fast Distributed MIS and Maximal Matching on Spatial and PLB-Bounded Scale-Free Networks: A Single-Event Meta-Theorem with Geometry and PLB-U/L/N

Ankit Chauhan
Distributed systems and fault tolerance
article

Fast Distributed MIS and Maximal Matching on Spatial and PLB-Bounded Scale-Free Networks: A Single-Event Meta-Theorem with Geometry and PLB-U/L/N

Ankit Chauhan
article en

Abstract

We prove an axiomatic meta-theorem yielding O(log log n)-round randomized algorithms for maximal independent set (MIS) and maximal matching on broad classes of scale-free networks. Our framework unifies two flavors: (i) geometry-driven rank-1 models (

Infosys (India) (IN)
Openalex Percentile: Top 66%
Distributed systems and fault tolerance
DOIOpen Access PDFOpenAlex
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Fast Distributed MIS and Maximal Matching on Spatial and PLB-Bounded Scale-Free Networks: A Single-Event Meta-Theorem with Geometry and PLB-U/L/N — Ankit Chauhan · (2025) | TGRS Research Map | TGRS