Buchumschlag

Approximation Ratio of the Min-Degree Greedy Algorithm for Maximum Independent Set on Interval and Chordal Graphs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Chaplick, Steven, Frohn, Martin, Kelk, Steven, Lottermoser, Johann, Mihalak, Matus
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

Snakes and Ladders: a Treewidth Story
von: Chaplick, Steven, et al.
Veröffentlicht: (2023)

Split-or-decompose: Improved FPT branching algorithms for maximum agreement forests
von: Mestel, David, et al.
Veröffentlicht: (2024)

A branch-&-price approach to the unrooted maximum agreement forest problem
von: Frohn, Martin, et al.
Veröffentlicht: (2024)

Reconstructing semi-directed level-1 networks using few quarnets
von: Frohn, Martin, et al.
Veröffentlicht: (2024)

GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility
von: Fahrbach, Matthew, et al.
Veröffentlicht: (2024)

Prime Factorization of the Kirchhoff Polynomial: Compact Enumeration of Arborescences
von: Mihalák, Matúš, et al.
Veröffentlicht: (2015)

Approximate Minimum Sum Colorings and Maximum $k$-Colorable Subgraphs of Chordal Graphs
von: DeHaan, Ian, et al.
Veröffentlicht: (2024)

A 4.509-Approximation Algorithm for Generalized Min Sum Set Cover
von: Bhangale, Amey, et al.
Veröffentlicht: (2026)

Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth
von: Wlodarczyk, Michal
Veröffentlicht: (2023)

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

Breaking the Barrier $2^k$ for Subset Feedback Vertex Set in Chordal Graphs
von: Bai, Tian, et al.
Veröffentlicht: (2022)

Engineering Algorithms for Dynamic Greedy Set Cover
von: Uzrad, Amitai
Veröffentlicht: (2026)

Revisiting Token Sliding on Chordal Graphs
von: Adak, Rajat, et al.
Veröffentlicht: (2025)

Cluster Vertex Deletion on Chordal Graphs
von: Cao, Yixin, et al.
Veröffentlicht: (2026)

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

Counting and Sampling Labeled Chordal Graphs in Polynomial Time
von: Hebert-Johnson, Ursula, et al.
Veröffentlicht: (2023)

Sampling Unlabeled Chordal Graphs in Expected Polynomial Time
von: Hébert-Johnson, Úrsula, et al.
Veröffentlicht: (2025)

Half-Approximating Maximum Dicut in the Streaming Setting
von: Azarmehr, Amir, et al.
Veröffentlicht: (2025)

Greedy Algorithms for Shortcut Sets and Hopsets
von: Bals, Ben, et al.
Veröffentlicht: (2025)

Improved Deterministic Distributed Maximum Weight Independent Set Approximation in Sparse Graphs
von: Gil, Yuval
Veröffentlicht: (2024)

Data Reductions for the Strong Maximum Independent Set Problem in Hypergraphs
von: Großmann, Ernestine, et al.
Veröffentlicht: (2026)

Maximum Independent Sets in Disk Graphs with Disks in Convex Position
von: Tkachenko, Anastasiia, et al.
Veröffentlicht: (2026)

Faster CONGEST Approximation Algorithms for Maximum Weighted Independent Set in Sparse Graphs
von: Faour, Salwa, et al.
Veröffentlicht: (2025)

Stable Approximation Algorithms for Dominating Set and Independent Set
von: de Berg, Mark, et al.
Veröffentlicht: (2024)

Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage
von: Balakrishnan, Girish, et al.
Veröffentlicht: (2024)

Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates
von: Mitrović, Slobodan, et al.
Veröffentlicht: (2026)

Approximating Maximum Cut on Interval Graphs and Split Graphs beyond Goemans-Williamson
von: Ahn, Jungho, et al.
Veröffentlicht: (2025)

Improved Approximation Algorithm for Maximum Balanced Biclique
von: Manurangsi, Pasin
Veröffentlicht: (2026)

Faster Min-Cost Flow and Approximate Tree Decomposition on Bounded Treewidth Graphs
von: Dong, Sally, et al.
Veröffentlicht: (2023)

Approximate Min-Sum Subset Convolution
von: Stoian, Mihail
Veröffentlicht: (2024)

Learning-augmented Maximum Independent Set
von: Braverman, Vladimir, et al.
Veröffentlicht: (2024)

Approximation Algorithms for Connected Maximum Coverage, Minimum Connected Set Cover, and Node-Weighted Group Steiner Tree
von: D'Angelo, Gianlorenzo, et al.
Veröffentlicht: (2025)

Maximum Coverage $k$-Antichains and Chains: A Greedy Approach
von: Cáceres, Manuel, et al.
Veröffentlicht: (2025)

$O(\log n)$-Approximation Algorithms for Bipartiteness Ratio
von: Soma, Tasuku, et al.
Veröffentlicht: (2025)

An Improved Greedy Approximation for (Metric) $k$-Means
von: Charikar, Moses, et al.
Veröffentlicht: (2026)

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

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
von: Anand, Aditya, et al.
Veröffentlicht: (2025)

From Dynamic Programs to Greedy Algorithms
von: van Melkebeek, Dieter
Veröffentlicht: (2025)

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

Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
von: Zheng, Da Wei, et al.
Veröffentlicht: (2023)