On Finding Critical Independent and Vertex Sets

DOI10.1137/S0895480191217569zbMath0798.05050OpenAlexW2076615361MaRDI QIDQ4296523

A. A. Ageev

Publication date: 20 October 1994

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480191217569

zbMATH Keywords

independent setcriticalpolynomial solvable

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

Critical sets, crowns and local maximum independent sets ⋮ Critical and maximum independent sets of a graph ⋮ Critical independent sets and König-Egerváry graphs ⋮ The critical independence number and an independence decomposition ⋮ Using critical sets to solve the maximum independent set problem ⋮ Level of repair analysis and minimum cost homomorphisms of graphs ⋮ On the Power of Simple Reductions for the Maximum Independent Set Problem ⋮ Introduction to the Maximum Solution Problem

This page was built for publication: On Finding Critical Independent and Vertex Sets