Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems
From MaRDI portal
Publication:4713055
DOI10.1137/0403037zbMath0756.05095OpenAlexW2054991375MaRDI QIDQ4713055
Publication date: 25 June 1992
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/36a711cb6397f93daf1643d60011d81e423f7727
Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (24)
Relations between the differential and parameters in graphs ⋮ On some conjectures concerning critical independent sets of a graph ⋮ Critical independent sets of König-Egerváry graphs ⋮ Critical sets, crowns and local maximum independent sets ⋮ On the critical difference of almost bipartite graphs ⋮ Some more updates on an annihilation number conjecture: pros and cons ⋮ Critical sets in bipartite graphs ⋮ 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 ⋮ Enumerating conjugacy classes of graphical groups over finite fields ⋮ On critical difference, independence number and matching number of graphs ⋮ Using critical sets to solve the maximum independent set problem ⋮ On the differential polynomial of a graph ⋮ A characterization of Konig-Egervary graphs using a common property of all maximum matchings ⋮ Problems on matchings and independent sets of a graph ⋮ Level of repair analysis and minimum cost homomorphisms of graphs ⋮ On the intersection of all critical sets of a unicyclic graph ⋮ On the Power of Simple Reductions for the Maximum Independent Set Problem ⋮ Monotonic properties of collections of maximum independent sets of a graph ⋮ A-differentials and total domination in graphs ⋮ The differential of the strong product graphs ⋮ Introduction to the Maximum Solution Problem ⋮ \(\beta\)-differential of a graph
This page was built for publication: Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems
