Imagen de Portada

Validating a PTAS for Triangle-Free 2-Matching via a Simple Decomposition Theorem

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Kobayashi, Yusuke, Noguchi, Takashi
Formato:	Preprint
Publicado:	2024
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

A PTAS for Weighted Triangle-free 2-Matching
por: Bosch-Calvo, Miguel, et al.
Publicado: (2026)

An Approximation Algorithm for 2-Vertex-Connectivity via Cycle-Restricted 2-Edge-Covers
por: Kobayashi, Yusuke, et al.
Publicado: (2026)

A Simple PTAS for Weighted $k$-means and Sensor Coverage
por: Pareek, Akash, et al.
Publicado: (2025)

NP-Hardness and a PTAS for the Pinwheel Problem
por: Kleinberg, Robert, et al.
Publicado: (2026)

Non-Adaptive Evaluation of $k$-of-$n$ Functions: Tight Gap and a Unit-Cost PTAS
por: Nielsen, Mads Anker, et al.
Publicado: (2025)

NP-hardness and a PTAS for the Euclidean Steiner Line Problem
por: Bartlmae, Simon, et al.
Publicado: (2024)

Simple Algorithms for Bad Triangle Transversals with Applications to Correlation Clustering
por: Adriaens, Florian, et al.
Publicado: (2026)

Subquadratic Submodular Maximization with a General Matroid Constraint
por: Kobayashi, Yusuke, et al.
Publicado: (2024)

Fully Dynamic Algorithms for Coloring Triangle-Free Graphs
por: Assadi, Sepehr, et al.
Publicado: (2026)

Simple Length-Constrained Expander Decompositions
por: Bodwin, Greg, et al.
Publicado: (2025)

Finding Spanning Trees with Perfect Matchings
por: Bérczi, Kristóf, et al.
Publicado: (2024)

A PTAS for Travelling Salesman Problem with Neighbourhoods Over Parallel Line Segments of Similar Length
por: Ghaseminia, Benyamin, et al.
Publicado: (2025)

Triangle Detection in H-Free Graphs
por: Abboud, Amir, et al.
Publicado: (2025)

Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
por: Chen, Daoyuan, et al.
Publicado: (2024)

Distributed Approximate Maximum Matching and Minimum Vertex Cover via Generalized Graph Decomposition
por: Davies-Peck, Peter
Publicado: (2026)

Separator Theorem for Minor-Free Graphs in Linear Time
por: Bonnet, Édouard, et al.
Publicado: (2025)

A Simple Deterministic Reduction From Gomory-Hu Tree to Maxflow and Expander Decomposition
por: Gutenberg, Maximilian Probst, et al.
Publicado: (2025)

An Improved Approximation Algorithm for Metric Triangle Packing
por: Zhao, Jingyang, et al.
Publicado: (2024)

Cover Edge-Based Novel Triangle Counting
por: Bader, David A., et al.
Publicado: (2024)

A Decomposition Theorem for Dynamic Flows
por: Graf, Lukas, et al.
Publicado: (2024)

Triangle-free 2-matchings
por: Paluch, Katarzyna
Publicado: (2023)

Polynomial Kernels with Reachability for Weighted $d$-Matroid Intersection
por: Huang, Chien-Chung, et al.
Publicado: (2026)

Finding Triangles or Independent Sets; and Other Dual Pair Approximations
por: Dumitrescu, Adrian
Publicado: (2021)

Minimum Sum Coloring with Bundles in Trees and Bipartite Graphs
por: Ito, Takehiro, et al.
Publicado: (2025)

Near Uniform Triangle Sampling Over Adjacency List Graph Streams
por: Bishnu, Arijit, et al.
Publicado: (2024)

Maximum Bipartite Matching in $n^{2+o(1)}$ Time via a Combinatorial Algorithm
por: Chuzhoy, Julia, et al.
Publicado: (2024)

A Simple Dynamic Spanner via APSP
por: Kyng, Rasmus, et al.
Publicado: (2024)

Edge Arrival Online Matching: The Power of Free Disposal on Acyclic Graphs
por: Jiang, Tianle, et al.
Publicado: (2024)

Arboricity and Random Edge Queries Matter for Triangle Counting using Sublinear Queries
por: Bishnu, Arijit, et al.
Publicado: (2025)

Publishing Below-Threshold Triangle Counts under Local Weight Differential Privacy
por: Pfisterer, Kevin, et al.
Publicado: (2026)

Fast exact algorithms via the Matrix Tree Theorem
por: Arvind, V., et al.
Publicado: (2025)

Triangle-Covered Graphs: Algorithms, Complexity, and Structure
por: Madani, Amirali, et al.
Publicado: (2025)

On the Structural Parameterizations of 2-Club with Triangle Constraints
por: Jacob, Ashwin, et al.
Publicado: (2025)

DTC: Real-Time and Accurate Distributed Triangle Counting in Fully Dynamic Graph Streams
por: Xuan, Wei, et al.
Publicado: (2025)

How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs
por: Conroy, Jonathan, et al.
Publicado: (2025)

Graph Coloring Below Guarantees via Co-Triangle Packing
por: Akmal, Shyan, et al.
Publicado: (2025)

A Sierpinski Triangle Data Structure for Efficient Array Value Update and Prefix Sum Calculation
por: Harrison, Brent, et al.
Publicado: (2024)

Proportionally Fair Matching via Randomized Rounding
por: Duppala, Sharmila, et al.
Publicado: (2024)

Course Allocation with Credits via Stable Matching
por: Rodríguez, José, et al.
Publicado: (2025)

Faster Semi-streaming Matchings via Alternating Trees
por: Mitrović, Slobodan, et al.
Publicado: (2024)