A bottom-up method and fast algorithms for Max Independent Set

DOI10.1007/978-3-642-13731-0_7zbMATH Open1285.68060DBLPconf/swat/BourgeoisEPR10OpenAlexW1490222502WikidataQ56335602 ScholiaQ56335602MaRDI QIDQ3569879FDOQ3569879

Authors: Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos, Johan M. M. Van Rooij 

Publication date: 22 June 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-13731-0_7

Recommendations

• Fast algorithms for max independent set
• Further Improvement on Maximum Independent Set in Degree-4 Graphs
• Exact algorithms for maximum independent set
• Exact Algorithms for Maximum Independent Set
• scientific article; zbMATH DE number 1305487

zbMATH Keywords

exact algorithmsbottom-up methodMax Independent Set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cited In (9)

• Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
• Fully Dynamic Maximal Independent Set with Sublinear in n Update Time
• Sharp separation and applications to exact and parameterized algorithms
• Exact algorithms for dominating set
• Fully dynamic maximal independent set with sublinear update time
• Exact Algorithms for Maximum Independent Set
• A fine-grained analysis of a simple independent set algorithm
• Exponential Time Complexity of Weighted Counting of Independent Sets
• Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation

This page was built for publication: A bottom-up method and fast algorithms for Max Independent Set

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