Cover Image

Geometric Bipartite Matching is in NC

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bhore, Sujoy, Equbal, Sarfaraz, Gurjar, Rohit
Format:	Preprint
Published:	2024
Subjects:	Computational Geometry Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Fractional Linear Matroid Matching is in quasi-NC
by: Gurjar, Rohit, et al.
Published: (2024)

Fully Dynamic Geometric Vertex Cover and Matching
by: Bhore, Sujoy, et al.
Published: (2024)

Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching
by: Bhore, Sujoy, et al.
Published: (2024)

Pathways to Tractability for Geometric Thickness
by: Depian, Thomas, et al.
Published: (2024)

The Parameterized Complexity of Geometric 1-Planarity
by: Firbas, Alexander
Published: (2026)

Online Epsilon Net and Piercing Set for Geometric Concepts
by: Bhore, Sujoy, et al.
Published: (2024)

Improved Online Hitting Set Algorithms for Structured and Geometric Set Systems
by: Bhore, Sujoy, et al.
Published: (2026)

Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings
by: Bhore, Sujoy, et al.
Published: (2023)

Light Spanners with Small Hop-Diameter
by: Bhore, Sujoy, et al.
Published: (2025)

Completeness Theorems for k-SUM and Geometric Friends: Deciding Fragments of Integer Linear Arithmetic
by: Gokaj, Geri, et al.
Published: (2025)

Kidney Exchange: Faster Parameterized Algorithms and Tighter Lower Bounds
by: Banik, Aritra, et al.
Published: (2025)

Improved Hardness of Approximation for Geometric Bin Packing
by: Ray, Arka, et al.
Published: (2023)

Approximation Schemes for Geometric Knapsack for Packing Spheres and Fat Objects
by: Acharya, Pritam, et al.
Published: (2024)

On Subexponential Parameterized Algorithms for Steiner Tree on Intersection Graphs of Geometric Objects
by: Bhore, Sujoy, et al.
Published: (2025)

On Saxe's theorems about the complexity of the Distance Geometry Problem
by: Kupperschmitt, Maël, et al.
Published: (2025)

Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds
by: Bhore, Sujoy, et al.
Published: (2026)

Complexity of 2D Snake Cube Puzzles
by: MIT Hardness Group, et al.
Published: (2024)

Constrained Boundary Labeling
by: Depian, Thomas, et al.
Published: (2024)

Minimum Selective Subset on Some Graph Classes
by: Manna, Bubai
Published: (2025)

On the complexity of embedding in graph products
by: Biedl, Therese, et al.
Published: (2023)

Counting Triangulations of Fixed Cardinal Degrees
by: Chambers, Erin, et al.
Published: (2025)

Push-1 is PSPACE-complete, and the automated verification of motion planning gadgets
by: DeStefano, Zachary, et al.
Published: (2025)

Query-Efficient Fixpoints of $\ell_p$-Contractions
by: Haslebacher, Sebastian, et al.
Published: (2025)

Tighter Bounds for the Randomized Polynomial-Time Simplex Algorithm for Linear Programming
by: Gibor, Daniel
Published: (2025)

Freeze-Tag is NP-hard in 2D with $L_1$ distance
by: Silva, Lucas de Oliveira, et al.
Published: (2025)

On the hardness of finding normal surfaces
by: Burton, Benjamin A., et al.
Published: (2019)

Realizing Metric Spaces with Convex Obstacles
by: Kisfaludi-Bak, Sándor, et al.
Published: (2025)

Recognizing Visibility Graphs of Polygons with Holes and Internal-External Visibility Graphs of Polygons
by: Boomari, Hossein, et al.
Published: (2018)

Minimum Selective Subset on Unit Disk Graphs and Circle Graphs
by: Manna, Bubai
Published: (2025)

The Complexity of Drawing Graphs on Few Lines and Few Planes
by: Chaplick, Steven, et al.
Published: (2016)

On the complexity of covering points by guillotine cuts
by: Garijo, Delia, et al.
Published: (2026)

Bipartite Matching is in Catalytic Logspace
by: Agarwala, Aryan, et al.
Published: (2025)

Fair Interval Scheduling of Indivisible Chores
by: Equbal, Sarfaraz, et al.
Published: (2024)

Bounds for Geometric rank in Terms of Subrank
by: Chen, Qiyuan, et al.
Published: (2025)

Sparse Bounded Hop-Spanners for Geometric Intersection Graphs
by: Bhore, Sujoy, et al.
Published: (2025)

Undecidability of Translational Tiling with Three Tiles
by: Yang, Chan, et al.
Published: (2024)

Translational Aperiodic Sets of 7 Polyominoes
by: Yang, Chao, et al.
Published: (2024)

Dynamic Light Spanners in Doubling Metrics
by: Bhore, Sujoy, et al.
Published: (2026)

Disrupting Bipartite Trading Networks: Matching for Revenue Maximization
by: D'Amico-Wong, Luca, et al.
Published: (2024)

Characterizing and Testing Principal Minor Equivalence of Matrices
by: Chatterjee, Abhranil, et al.
Published: (2024)