Approximation ratio of the min-degree greedy algorithm for maximum independent set on interval and chordal graphs

DOI10.1016/J.DAM.2024.09.009MaRDI QIDQ6648269

Matúš Mihalák, Johann Lottermoser, Martin Frohn, Steven Chaplick, Steven Kelk

Publication date: 4 December 2024

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

chordal graphsapproximation algorithmsinterval graphsgreedy algorithmsmaximum independent set

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• It is hard to know when greedy is good for finding independent sets
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• Approximation algorithms for the weighted independent set problem in sparse graphs
• Interval graphs and related topics
• Optimization, approximation, and complexity classes
• A note on greedy algorithms for the maximum weighted independent set problem
• Algorithmic graph theory and perfect graphs
• Graph Theory
• Interval scheduling: A survey
• Algorithmic Aspects of Vertex Elimination on Graphs
• An Analysis of the Greedy Heuristic for Independence Systems
• The leafage of a chordal graph
• Ultimate greedy approximation of independent sets in subcubic graphs
• Greedy in Approximation Algorithms
• Scheduling Split Intervals
• Simple and local independent set approximation
• Greedy approximations of independent sets in low degree graphs

This page was built for publication: Approximation ratio of the min-degree greedy algorithm for maximum independent set on interval and chordal graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6648269)