Ultimate greedy approximation of independent sets in subcubic graphs
type: Item
instance of: scholarly article
title: Ultimate greedy approximation of independent sets in subcubic graphs
author: Piotr Krysta
author: Mathieu Mari
author: Nan Zhi
published in: Algorithmica
publication date: 2024-10-24T00:00:00Z
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 05Cxx
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 7931161
zbMATH Keywords: approximation algorithms
zbMATH Keywords: greedy algorithms
zbMATH Keywords: independent set problem
zbMATH Keywords: bounded degree graphs
MaRDI profile type: MaRDI publication profile
cites work: Some APX-completeness results for cubic graphs
cites work: Q3002828
cites work: On the Lovász Theta function for Independent Sets in Sparse Graphs
cites work: Q5668821
cites work: On approximation properties of the independent set problem for low degree graphs
cites work: Q3128896
cites work: It is hard to know when greedy is good for finding independent sets
cites work: Approximating maximum independent sets by excluding subgraphs
cites work: Approximation Resistance from Pairwise-Independent Subgroups
cites work: Fundamentals of Computation Theory
cites work: Structural Information and Communication Complexity
cites work: The Monotone Satisfiability Problem with Bounded Variable Appearances
cites work: Improved approximations for maximum independent set via approximation chains
cites work: Q5638352
cites work: Approximating Maximum Clique by Removing Subgraphs
cites work: On the independence number of random cubic graphs
cites work: Some simplified NP-complete graph problems
cites work: Q5620621
cites work: Greed is good: approximating independent sets in sparse and bounded-degree graphs
cites work: Improved approximations of independent sets in bounded-degree graphs
cites work: Q4698692
cites work: Greed is good: Approximating independent sets in sparse and bounded-degree graphs
cites work: Greedy approximations of independent sets in low degree graphs
cites work: Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
cites work: Efficient bounds for the stable set, vertex cover and set packing problems
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: On the complexity of \(k\)-SAT
cites work: Q4065570
cites work: Reducibility among Combinatorial Problems
cites work: On Syntactic versus Computational Views of Approximability
cites work: Three short proofs in graph theory
cites work: Q3826581
cites work: Vertex packings: Structural properties and algorithms
cites work: A note on the independence number of triangle-free graphs
cites work: On Approximate Solutions for Combinatorial Optimization Problems
cites work: Q5781249
cites work: Linear degree extractors and the inapproximability of max clique and chromatic number
DOI: 10.1007/S00453-024-01268-7
description: scientific article; zbMATH DE number 7931161