Cover Image

Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Galby, Esther, Munaro, Andrea, Yang, Shizhou
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms Computational Geometry Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Polynomial-time approximation schemes for induced subgraph problems on fractionally tree-independence-number-fragile graphs
by: Galby, Esther, et al.
Published: (2024)

Maximum list $r$-colorable induced subgraphs in $kP_3$-free graphs
by: Galby, Esther, et al.
Published: (2025)

Computing Tree Decompositions with Small Independence Number
by: Dallard, Clément, et al.
Published: (2022)

On algorithmic applications of sim-width and mim-width of $(H_1, H_2)$-free graphs
by: Munaro, Andrea, et al.
Published: (2022)

Approximately: Independence Implies Vertex Cover
by: Har-Peled, Sariel
Published: (2023)

Tree Independence Number IV. Even-hole-free Graphs
by: Chudnovsky, Maria, 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)

Solving Problems on Generalized Convex Graphs via Mim-Width
by: Bonomo-Braberman, Flavia, et al.
Published: (2020)

On Computing Vertex Connectivity of 1-Plane Graphs
by: Biedl, Therese, et al.
Published: (2022)

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

On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and other applications
by: Filtser, Arnold
Published: (2024)

Maximum Independent Sets in Disk Graphs with Disks in Convex Position
by: Tkachenko, Anastasiia, et al.
Published: (2026)

Polynomial-Delay Enumeration of Large Maximal Common Independent Sets in Two Matroids and Beyond
by: Kobayashi, Yasuaki, et al.
Published: (2023)

Small Independent Sets versus Small Separator in Geometric Intersection Graphs
by: Marin, Malory, et al.
Published: (2026)

Approximating the Maximum Independent Set of Convex Polygons with a Bounded Number of Directions
by: Grandoni, Fabrizio, et al.
Published: (2024)

Approximation Schemes and Structural Barriers for the Two-Dimensional Knapsack Problem with Rotations
by: Kar, Debajyoti, et al.
Published: (2026)

Quadratic-Time Algorithm for the Maximum-Weight $(k, \ell)$-Sparse Subgraph Problem
by: Deák, Bence, et al.
Published: (2025)

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

Improved Approximation Algorithms for Three-Dimensional Bin Packing
by: Kar, Debajyoti, et al.
Published: (2025)

A Dichotomy for 1-Planarity with Restricted Crossing Types Parameterized by Treewidth
by: Cabello, Sergio, et al.
Published: (2025)

Zone Theorem for Arrangements in three dimensions
by: Saxena, Sanjeev
Published: (2020)

Stable Approximation Algorithms for Dominating Set and Independent Set
by: de Berg, Mark, et al.
Published: (2024)

An $O(n \log n)$-Time Approximation Scheme for Geometric Many-to-Many Matching
by: Bandyapadhyay, Sayan, et al.
Published: (2024)

A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs
by: S, Ajaykrishnan E, et al.
Published: (2025)

Faster Approximation Scheme for Euclidean $k$-TSP
by: van Wijland, Ernest, et al.
Published: (2023)

Solving NP-hard Problems on \textsc{GaTEx} Graphs: Linear-Time Algorithms for Perfect Orderings, Cliques, Colorings, and Independent Sets
by: Hellmuth, Marc, et al.
Published: (2023)

Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering
by: Gadekar, Ameet, et al.
Published: (2025)

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

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

Structure and Independence in Hyperbolic Uniform Disk Graphs
by: Bläsius, Thomas, et al.
Published: (2024)

Faster Algorithms for Sparse ILP and Hypergraph Multi-Packing/Multi-Cover Problems
by: Gribanov, Dmitry, et al.
Published: (2022)

The Squishy Grid Problem
by: Cai, Zixi, et al.
Published: (2025)

Fast Approximation Algorithms for Euclidean Minimum Weight Perfect Matching
by: Hougardy, Stefan, et al.
Published: (2024)

O(1)-Distortion Planar Emulators for String Graphs
by: Chang, Hsien-Chih, et al.
Published: (2025)

Weighted Clique and Independent Set in Edge-Distant Hereditary Graphs
by: Srinivasan, Eshwar, et al.
Published: (2026)

Graph Classes Closed under Self-intersection
by: Dabrowski, Konrad K., et al.
Published: (2025)

FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters Clustering
by: Grandoni, Fabrizio, et al.
Published: (2026)

An Improved Upper Bound for the Euclidean TSP Constant Using Band Crossovers
by: Gaudio, Julia, et al.
Published: (2026)

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

On Approximating the Weighted Region Problem in Square Tessellations
by: Kakimura, Naonori, et al.
Published: (2024)