A fine-grained analysis of a simple independent set algorithm

DOI10.4230/LIPICS.FSTTCS.2009.2326zbMATH Open1248.05202OpenAlexW2153667368MaRDI QIDQ2920136FDOQ2920136

Authors: Joachim Kneis, Alexander Langer, Peter Rossmanith 

Publication date: 24 October 2012

Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_dadd.html

Recommendations

• On the complexity of approximating the independent set problem
• Exact algorithms for maximum independent set
• Exact Algorithms for Maximum Independent Set
• A note on the random greedy independent set algorithm
• On the complexity of approximating the independent set problem (extended abstract)
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Probabilistic analysis of a parallel algorithm for finding maximal independent sets
• Publication:4864968
• A bottom-up method and fast algorithms for Max Independent Set
• Algorithms for maximum independent sets

zbMATH Keywords

exact algorithmsindependent setsatellitescomputer-aided proof

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Cited In (15)

• A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• A refined algorithm for maximum independent set in degree-4 graphs
• Exact algorithms for maximum weighted independent set on sparse graphs (extended abstract)
• Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
• An exact algorithm for maximum independent set in degree-5 graphs
• Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
• Maximum Weighted Independent Set: Effective Reductions and Fast Algorithms on Sparse Graphs
• Fast algorithms for max independent set
• Computing the differential of a graph: hardness, approximability and exact algorithms
• Exponential Time Complexity of Weighted Counting of Independent Sets
• Algorithmic Aspects of Upper Domination: A Parameterised Perspective
• The many facets of upper domination
• Exact algorithms for maximum independent set
• On independent sets and bicliques in graphs

This page was built for publication: A fine-grained analysis of a simple independent set algorithm

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