Image de couverture de livre

Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Lokshtanov, Daniel, Panolan, Fahad, Saurabh, Saket, Xue, Jie, Zehavi, Meirav
Format:	Preprint
Publié:	2024
Sujets:	Data Structures and Algorithms Computational Geometry
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Subexponential Parameterized Algorithms for Hitting Subgraphs
par: Lokshtanov, Daniel, et autres
Publié: (2024)

Parameterized Geometric Graph Modification with Disk Scaling
par: Fomin, Fedor V., et autres
Publié: (2024)

FPT Approximations for Connected Maximum Coverage
par: Inamdar, Tanmay, et autres
Publié: (2026)

Tight Parameterized (In)tractability of Layered Crossing Minimization: Subexponential Algorithms and Kernelization
par: Fomin, Fedor V., et autres
Publié: (2025)

Hybrid k-Clustering: Blending k-Median and k-Center
par: Fomin, Fedor V., et autres
Publié: (2024)

Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
par: Lokshtanov, Daniel, et autres
Publié: (2024)

Parameterized Saga of First-Fit and Last-Fit Coloring
par: Agrawal, Akanksha, et autres
Publié: (2024)

When far is better: The Chamberlin-Courant approach to obnoxious committee selection
par: Gupta, Sushmita, et autres
Publié: (2024)

FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii
par: Bandyapadhyay, Sayan, et autres
Publié: (2023)

Parameterized Approximation for Capacitated $d$-Hitting Set with Hard Capacities
par: Lokshtanov, Daniel, et autres
Publié: (2024)

Parameterized Approximation of Rectangle Stabbing
par: Chu, Huairui, et autres
Publié: (2026)

A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs
par: S, Ajaykrishnan E, et autres
Publié: (2025)

Exact Algorithms for Clustered Planarity with Linear Saturators
par: Da Lozzo, Giordano, et autres
Publié: (2024)

Single-Source Shortest Path Problem in Weighted Disk Graphs
par: An, Shinwoo, et autres
Publié: (2025)

Minimum Temporal Spanners in Happy Graphs
par: Casteigts, Arnaud, et autres
Publié: (2026)

Path Contraction Faster than $2^n$
par: Agrawal, Akanksha, et autres
Publié: (2025)

Computing Diameter +1 in Truly Subquadratic Time for Unit-Disk Graphs
par: Chang, Hsien-Chih, et autres
Publié: (2024)

Maximum Independent Sets in Disk Graphs with Disks in Convex Position
par: Tkachenko, Anastasiia, et autres
Publié: (2026)

Dynamic Connectivity in Disk Graphs
par: Baumann, Alexander, et autres
Publié: (2021)

An $O(n \log n)$-Time Approximation Scheme for Geometric Many-to-Many Matching
par: Bandyapadhyay, Sayan, et autres
Publié: (2024)

Parameterized Algorithms for Minimum Sum Vertex Cover
par: Aute, Shubhada, et autres
Publié: (2024)

Computing Maximum Cliques in Unit Disk Graphs
par: Tkachenko, Anastasiia, et autres
Publié: (2025)

Shortest Path Separators in Unit Disk Graphs
par: Harb, Elfarouk, et autres
Publié: (2024)

Sparse Outerstring Graphs Have Logarithmic Treewidth
par: An, Shinwoo, et autres
Publié: (2024)

An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs
par: Brewer, Bruce W., et autres
Publié: (2025)

An Improved Algorithm for Shortest Paths in Weighted Unit-Disk Graphs
par: Brewer, Bruce W., et autres
Publié: (2024)

Computing Dominating Sets in Disk Graphs with Centers in Convex Position
par: Tkachenko, Anastasiia, et autres
Publié: (2026)

ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs
par: An, Shinwoo, et autres
Publié: (2024)

Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs
par: Kisfaludi-Bak, Sándor, et autres
Publié: (2026)

Learning Small Decision Trees with Few Outliers: A Parameterized Perspective
par: Gahlawat, Harmender, et autres
Publié: (2025)

(Almost-)Optimal FPT Algorithm and Kernel for $T$-Cycle on Planar Graphs
par: Gahlawat, Harmender, et autres
Publié: (2025)

Better Diameter Algorithms for Bounded VC-dimension Graphs and Geometric Intersection Graphs
par: Duraj, Lech, et autres
Publié: (2023)

Subexponential Algorithms for Clique Cover on Unit Disk and Unit Ball Graphs
par: Koana, Tomohiro, et autres
Publié: (2024)

Algorithms for Euclidean Distance Matrix Completion: Exploiting Proximity to Triviality
par: Fomin, Fedor V., et autres
Publié: (2026)

Subcoloring of (Unit) Disk Graphs
par: Marin, Malory, et autres
Publié: (2025)

Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints
par: Inamdar, Tanmay, et autres
Publié: (2024)

Fixed-Parameter Tractability of Hedge Cut
par: Fomin, Fedor V., et autres
Publié: (2024)

Revisiting Graph Modification via Disk Scaling: From One Radius to Interval-Based Radii
par: Depian, Thomas, et autres
Publié: (2026)

How to Make Knockout Tournaments More Popular?
par: Chaudhary, Juhi, et autres
Publié: (2023)

When Distances Lie: Euclidean Embeddings in the Presence of Outliers and Distance Violations
par: Bentert, Matthias, et autres
Publié: (2025)