A Fine-grained Analysis of a Simple Independent Set Algorithm
From MaRDI portal
Publication:2920136
DOI10.4230/LIPIcs.FSTTCS.2009.2326zbMath1248.05202OpenAlexW2153667368MaRDI QIDQ2920136
Joachim Kneis, Alexander Langer, Peter Rossmanith
Publication date: 24 October 2012
Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_dadd.html
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ A refined algorithm for maximum independent set in degree-4 graphs ⋮ A novel parameterised approximation algorithm for \textsc{minimum vertex cover} ⋮ An exact algorithm for maximum independent set in degree-5 graphs ⋮ Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover ⋮ Fast algorithms for max independent set ⋮ On independent sets and bicliques in graphs ⋮ Exact algorithms for maximum weighted independent set on sparse graphs (extended abstract) ⋮ The many facets of upper domination ⋮ On computing the minimum 3-path vertex cover and dissociation number of graphs ⋮ Computing the differential of a graph: hardness, approximability and exact algorithms ⋮ Exact algorithms for maximum independent set ⋮ Exponential Time Complexity of Weighted Counting of Independent Sets ⋮ Algorithmic Aspects of Upper Domination: A Parameterised Perspective
