Cover Image

A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	S, Ajaykrishnan E, Ganian, Robert, Lokshtanov, Daniel, Surianarayanan, Vaishali
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Computational Geometry
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Linear Layouts Revisited: Stacks, Queues, and Exact Algorithms
by: Depian, Thomas, et al.
Published: (2025)

Parameterized Approximation of Rectangle Stabbing
by: Chu, Huairui, et al.
Published: (2026)

Beyond Exact Fairness: Envy-Free Incomplete Connected Fair Division
by: S, Ajaykrishnan E, et al.
Published: (2025)

Parameterized Approximation for Capacitated $d$-Hitting Set with Hard Capacities
by: Lokshtanov, Daniel, et al.
Published: (2024)

Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3
by: Lokshtanov, Daniel, et al.
Published: (2024)

Exact Algorithms for Clustered Planarity with Linear Saturators
by: Da Lozzo, Giordano, et al.
Published: (2024)

Sampling Unlabeled Chordal Graphs in Expected Polynomial Time
by: Hébert-Johnson, Úrsula, et al.
Published: (2025)

The Peculiarities of Extending Queue Layouts
by: Depian, Thomas, et al.
Published: (2025)

The Parameterized Complexity of Extending Stack Layouts
by: Depian, Thomas, et al.
Published: (2024)

Counting and Sampling Labeled Chordal Graphs in Polynomial Time
by: Hebert-Johnson, Ursula, et al.
Published: (2023)

An Algorithmic Solution for Computing Circle Intersection Areas and its Applications to Wireless Communications
by: Librino, Federico, et al.
Published: (2012)

Induced Minors and Coarse Tree Decompositions
by: Chudnovsky, Maria, et al.
Published: (2026)

Clustering with Set Outliers and Applications in Relational Clustering
by: Surianarayanan, Vaishali, et al.
Published: (2025)

2-Layer Fan-Planarity in Polynomial Time
by: Kobayashi, Yasuaki, et al.
Published: (2025)

A Tight Subexponential-time Algorithm for Two-Page Book Embedding
by: Ganian, Robert, et al.
Published: (2024)

Non-crossing Hamiltonian Paths and Cycles in Output-Polynomial Time
by: Eppstein, David
Published: (2023)

Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension
by: Chan, Timothy M., et al.
Published: (2025)

FPT Constant Approximation Algorithms for Colorful Sum of Radii
by: Liu, Shuilian, et al.
Published: (2025)

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

Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs
by: Galby, Esther, et al.
Published: (2023)

Coordinated Motion Planning is FPT on Discretized Simple Polygons
by: Deligkas, Argyrios, et al.
Published: (2026)

Better Diameter Algorithms for Bounded VC-dimension Graphs and Geometric Intersection Graphs
by: Duraj, Lech, et al.
Published: (2023)

An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs
by: Brewer, Bruce W., et al.
Published: (2025)

Robust Algorithms for Path and Cycle Problems in Geometric Intersection Graphs
by: Marin, Malory, et al.
Published: (2025)

An Improved Algorithm for Shortest Paths in Weighted Unit-Disk Graphs
by: Brewer, Bruce W., et al.
Published: (2024)

ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs
by: An, Shinwoo, et al.
Published: (2024)

A Subquadratic Time Approximation Algorithm for Individually Fair k-Center
by: Ebbens, Matthijs, et al.
Published: (2024)

$k$-PCA for (non-squared) Euclidean Distances: Polynomial Time Approximation
by: Greenhut, Daniel, et al.
Published: (2025)

Subexponential Algorithms for Clique Cover on Unit Disk and Unit Ball Graphs
by: Koana, Tomohiro, et al.
Published: (2024)

Using Ray-shooting Queries for Sublinear Algorithms for Dominating Sets in RDV Graphs
by: Biedl, Therese, et al.
Published: (2026)

Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Bipartite Tournaments
by: Kumar, Mithilesh, et al.
Published: (2024)

Computing Diameter +1 in Truly Subquadratic Time for Unit-Disk Graphs
by: Chang, Hsien-Chih, et al.
Published: (2024)

Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs
by: Kisfaludi-Bak, Sándor, et al.
Published: (2026)

Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-and-Bifurcate Technique
by: Chan, Timothy M., et al.
Published: (2025)

Morphing Planar Graph Drawings Through 3D
by: Buchin, Kevin, et al.
Published: (2022)

Bilateral Treewidth for QBF: Where Strategies and Resolution Meet
by: Ganian, Robert, et al.
Published: (2026)

Even Faster Algorithm for the Chamfer Distance
by: Feng, Ying, et al.
Published: (2025)

Approximation Algorithms for Smallest Intersecting Balls
by: Zheng, Jiaqi, et al.
Published: (2024)

Online Algorithms for Geometric Independent Set
by: De, Minati, et al.
Published: (2026)

Fast Algorithms for Minimum Homology Basis
by: Dhar, Amritendu, et al.
Published: (2021)