Imagen de Portada

Finding Triangles or Independent Sets; and Other Dual Pair Approximations

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Dumitrescu, Adrian
Formato:	Preprint
Publicado:	2021
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 Strongly Subcubic Combinatorial Algorithm for Triangle Detection with Applications
por: Dumitrescu, Adrian
Publicado: (2024)

Finding Small Complete Subgraphs Efficiently
por: Chen, Ke, et al.
Publicado: (2023)

Finding Shortest Reconfiguration Sequences on Independent Set Polytopes
por: Cardinal, Jean, et al.
Publicado: (2026)

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

On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
por: Ghoshal, Suprovat, et al.
Publicado: (2026)

Approximation Ratio of the Min-Degree Greedy Algorithm for Maximum Independent Set on Interval and Chordal Graphs
por: Chaplick, Steven, et al.
Publicado: (2024)

The clustered Sparrow algorithm
por: Dumitrescu, Cristian
Publicado: (2018)

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

A Tolerant Independent Set Tester
por: Seth, Cameron
Publicado: (2025)

Solution Discovery for Vertex Cover, Independent Set, Dominating Set, and Feedback Vertex Set
por: Saito, Rin, et al.
Publicado: (2025)

Optimal Neighborhood Exploration for Dynamic Independent Sets
por: Borowitz, Jannick, et al.
Publicado: (2024)

On the Complexity of Finding Approximate LCS of Multiple Strings
por: Hasibi, Hamed, et al.
Publicado: (2025)

New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
por: Dory, Michal, et al.
Publicado: (2022)

All-Pairs Suffix-Prefix on Fully Dynamic Set of Strings
por: Kikuchi, Masaru, et al.
Publicado: (2024)

Sublinear Metric Steiner Forest via Maximal Independent Set
por: Mahabadi, Sepideh, et al.
Publicado: (2025)

Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs
por: Bieliński, Paweł Rafał, et al.
Publicado: (2026)

Data Reductions for the Strong Maximum Independent Set Problem in Hypergraphs
por: Großmann, Ernestine, et al.
Publicado: (2026)

Half-Approximating Maximum Dicut in the Streaming Setting
por: Azarmehr, Amir, et al.
Publicado: (2025)

Logarithmic Approximations for Fair k-Set Selection
por: Li, Shi, et al.
Publicado: (2025)

Finding Maximum Weight 2-Packing Sets on Arbitrary Graphs
por: Borowitz, Jannick, et al.
Publicado: (2025)

Finding a Largest-Area Triangle in a Terrain in Near-Linear Time
por: Cabello, Sergio, et al.
Publicado: (2021)

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

Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs
por: Kothari, Pravesh, et al.
Publicado: (2024)

Almost-Uniform Edge Sampling: Leveraging Independent-Set and Local Graph Queries
por: Adar, Tomer, et al.
Publicado: (2026)

Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
por: Solomon, Shay, et al.
Publicado: (2023)

A Generalized Binary Tree Mechanism for Differentially Private Approximation of All-Pair Distances
por: Dinitz, Michael, et al.
Publicado: (2025)

On Finding $\ell$-th Smallest Perfect Matchings
por: Maalouly, Nicolas El, et al.
Publicado: (2025)

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

Fault-Tolerant Approximate Distance Oracles with a Source Set
por: Dey, Dipan, et al.
Publicado: (2025)

Approximate Spanning Tree Counting from Uncorrelated Edge Sets
por: Liu, Yang P., et al.
Publicado: (2025)

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

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

A Comprehensive Survey of Data Reduction Rules for the Maximum Weighted Independent Set Problem
por: Großmann, Ernestine, et al.
Publicado: (2024)

From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem
por: Eiben, Eduard, et al.
Publicado: (2024)

When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set Queries
por: Adar, Tomer, et al.
Publicado: (2026)

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

Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching
por: Bhore, Sujoy, et al.
Publicado: (2024)

Deterministic $(2/3-\varepsilon)$-Approximation of Matroid Intersection Using Nearly-Linear Independence-Oracle Queries
por: Terao, Tatsuya
Publicado: (2024)

Approximately: Independence Implies Vertex Cover
por: Har-Peled, Sariel
Publicado: (2023)

A 4.509-Approximation Algorithm for Generalized Min Sum Set Cover
por: Bhangale, Amey, et al.
Publicado: (2026)