On the independent set problem in random graphs

DOI10.1080/00207160.2014.976210zbMath1334.05108arXiv1308.1556OpenAlexW2168519036WikidataQ56210439 ScholiaQ56210439MaRDI QIDQ2804023

Yinglei Song

Publication date: 27 April 2016

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1308.1556

zbMATH Keywords

random graphsindependent setexact algorithmparameterized algorithm

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Strong computational lower bounds via parameterized complexity
• An effective local search for the maximum clique problem
• Approximating maximum independent sets by excluding subgraphs
• Approximation algorithms for combinatorial problems
• On independent sets in random graphs
• The importance of being biased
• Linear FPT reductions and computational lower bounds
• Measure and conquer
• Finding a Maximum Independent Set in a Sparse Random Graph
• An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem
• On colouring random graphs
• Approximating Maximum Clique by Removing Subgraphs
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Reactive local search for the maximum clique problem

This page was built for publication: On the independent set problem in random graphs