scientific article; zbMATH DE number 1182770

MaRDI QIDQ4400853zbMATH OpenFDO

Authors Ingo Schiermeyer

Publication date 25 October 1998

zbMATH Keywords

cliqueindependence numberindependent set

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1003268
• scientific article; zbMATH DE number 753971
• Improved approximations of independent sets in bounded-degree graphs
• Approximating maximum independent sets by excluding subgraphs
• Approximating maximum independent sets by excluding subgraphs

Cited in

(11)

• A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs
• Maximal independent sets in clique-free graphs
• scientific article; zbMATH DE number 1617260 (Why is no real title available?)
• An approximation algorithm for the maximum independent set problem in cubic planar graphs
• Rank and chromatic number of a graph
• Approximating Maximum Clique by Removing Subgraphs
• Improved lower bounds for the randomized Boppana-Halldórsson algorithm for MAXCLIQUE
• Independence in connected graphs
• Interpolating between bounds on the independence number
• A note on the greedy algorithm for finding independent sets of \(C_k\)-free graphs
• An optimal maximal independent set algorithm for bounded-independence graphs

This page was built for publication:

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