Buchumschlag

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

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Kobayashi, Yusuke, Noguchi, Takashi
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

A PTAS for Weighted Triangle-free 2-Matching
von: Bosch-Calvo, Miguel, et al.
Veröffentlicht: (2026)

An Approximation Algorithm for 2-Vertex-Connectivity via Cycle-Restricted 2-Edge-Covers
von: Kobayashi, Yusuke, et al.
Veröffentlicht: (2026)

A Simple PTAS for Weighted $k$-means and Sensor Coverage
von: Pareek, Akash, et al.
Veröffentlicht: (2025)

NP-Hardness and a PTAS for the Pinwheel Problem
von: Kleinberg, Robert, et al.
Veröffentlicht: (2026)

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

NP-hardness and a PTAS for the Euclidean Steiner Line Problem
von: Bartlmae, Simon, et al.
Veröffentlicht: (2024)

Simple Algorithms for Bad Triangle Transversals with Applications to Correlation Clustering
von: Adriaens, Florian, et al.
Veröffentlicht: (2026)

Subquadratic Submodular Maximization with a General Matroid Constraint
von: Kobayashi, Yusuke, et al.
Veröffentlicht: (2024)

Fully Dynamic Algorithms for Coloring Triangle-Free Graphs
von: Assadi, Sepehr, et al.
Veröffentlicht: (2026)

Simple Length-Constrained Expander Decompositions
von: Bodwin, Greg, et al.
Veröffentlicht: (2025)

Finding Spanning Trees with Perfect Matchings
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2024)

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

Triangle Detection in H-Free Graphs
von: Abboud, Amir, et al.
Veröffentlicht: (2025)

Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
von: Chen, Daoyuan, et al.
Veröffentlicht: (2024)

Distributed Approximate Maximum Matching and Minimum Vertex Cover via Generalized Graph Decomposition
von: Davies-Peck, Peter
Veröffentlicht: (2026)

Separator Theorem for Minor-Free Graphs in Linear Time
von: Bonnet, Édouard, et al.
Veröffentlicht: (2025)

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

An Improved Approximation Algorithm for Metric Triangle Packing
von: Zhao, Jingyang, et al.
Veröffentlicht: (2024)

Cover Edge-Based Novel Triangle Counting
von: Bader, David A., et al.
Veröffentlicht: (2024)

A Decomposition Theorem for Dynamic Flows
von: Graf, Lukas, et al.
Veröffentlicht: (2024)

Triangle-free 2-matchings
von: Paluch, Katarzyna
Veröffentlicht: (2023)

Polynomial Kernels with Reachability for Weighted $d$-Matroid Intersection
von: Huang, Chien-Chung, et al.
Veröffentlicht: (2026)

Finding Triangles or Independent Sets; and Other Dual Pair Approximations
von: Dumitrescu, Adrian
Veröffentlicht: (2021)

Minimum Sum Coloring with Bundles in Trees and Bipartite Graphs
von: Ito, Takehiro, et al.
Veröffentlicht: (2025)

Near Uniform Triangle Sampling Over Adjacency List Graph Streams
von: Bishnu, Arijit, et al.
Veröffentlicht: (2024)

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

A Simple Dynamic Spanner via APSP
von: Kyng, Rasmus, et al.
Veröffentlicht: (2024)

Edge Arrival Online Matching: The Power of Free Disposal on Acyclic Graphs
von: Jiang, Tianle, et al.
Veröffentlicht: (2024)

Arboricity and Random Edge Queries Matter for Triangle Counting using Sublinear Queries
von: Bishnu, Arijit, et al.
Veröffentlicht: (2025)

Publishing Below-Threshold Triangle Counts under Local Weight Differential Privacy
von: Pfisterer, Kevin, et al.
Veröffentlicht: (2026)

Fast exact algorithms via the Matrix Tree Theorem
von: Arvind, V., et al.
Veröffentlicht: (2025)

Triangle-Covered Graphs: Algorithms, Complexity, and Structure
von: Madani, Amirali, et al.
Veröffentlicht: (2025)

On the Structural Parameterizations of 2-Club with Triangle Constraints
von: Jacob, Ashwin, et al.
Veröffentlicht: (2025)

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

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

Graph Coloring Below Guarantees via Co-Triangle Packing
von: Akmal, Shyan, et al.
Veröffentlicht: (2025)

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

Proportionally Fair Matching via Randomized Rounding
von: Duppala, Sharmila, et al.
Veröffentlicht: (2024)

Course Allocation with Credits via Stable Matching
von: Rodríguez, José, et al.
Veröffentlicht: (2025)

Faster Semi-streaming Matchings via Alternating Trees
von: Mitrović, Slobodan, et al.
Veröffentlicht: (2024)