scientific article; zbMATH DE number 1251573

MaRDI QIDQ4229265zbMATHFDO

Authors N. V. R. Mahadev, Bruce Reed

Publication date 19 August 1999

zbMATH Keywords

NP-completenessNP-hardstable setstability number

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75)

Recommendations

• On vertex orderings and the stability number in triangle-free graphs
• scientific article; zbMATH DE number 817188
• scientific article; zbMATH DE number 1833095

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• k-Components, Clusters and Slicings in Graphs
• An inequality for the chromatic number of a graph
• An upper bound for the chromatic number of a graph and its application to timetabling problems
• Four classes of perfectly orderable graphs
• Polynomially solvable cases for the maximum stable set problem
• Smallest-last ordering and clustering and graph coloring algorithms

Cited in

(8)

• A note on \(\alpha\)-redundant vertices in graphs
• Extending the MAX algorithm for maximum independent set
• New properties of perfectly orderable graphs and strongly perfect graphs
• Stable sets in two subclasses of banner-free graphs
• Minimum degree algorithms for stability number
• On vertex orderings and the stability number in triangle-free graphs
• On sequential heuristic methods for the maximum independent set problem
• New sufficient conditions for \(\alpha\)-redundant vertices

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 Q4229265)