Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems

DOI10.1137/0403037MaRDI QIDQ4713055zbMATH OpenOpenAlexFDO

Authors Cun-Quan Zhang

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

zbMATH Keywords

critical independent setscritical vertex subsetssolvable in polynomial time

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35)

Recommendations

• On Finding Critical Independent and Vertex Sets
• Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs
• Finding independent sets in a graph using continuous multivariable polynomial formulations.
• Classes of subcubic planar graphs for which the independent set problem is polynomially solvable
• scientific article; zbMATH DE number 6460018
• THE CRITICAL PROBLEM FOR POLYMATROIDS
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• A sufficient condition to extend polynomial results for the maximum independent set problem
• Clique polynomials and independent set polynomials of graphs
• Independent domination in finitely defined classes of graphs: polynomial algorithms

Cited in

(31)

• Critical and maximum independent sets of a graph
• On the differential polynomial of a graph
• Problems on matchings and independent sets of a graph
• Critical independent sets and König-Egerváry graphs
• 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
• Monotonic properties of collections of maximum independent sets of a graph
• \(\beta\)-differential of a graph
• Using critical sets to solve the maximum independent set problem
• Level of repair analysis and minimum cost homomorphisms of graphs
• On some conjectures concerning critical independent sets of a graph
• On the power of simple reductions for the maximum independent set problem
• A-differentials and total domination in graphs
• Relations between the differential and parameters in graphs
• A characterization of König-Egerváry graphs using a common property of all maximum matchings
• Critical sets in bipartite graphs
• On Finding Critical Independent and Vertex Sets
• The differential of the strong product graphs
• A note on critical independence reductions
• Introduction to the Maximum Solution Problem
• Enumerating conjugacy classes of graphical groups over finite fields
• On critical difference, independence number and matching number of graphs
• The critical independence number and an independence decomposition
• The differential on graph operator \(\mathrm{R}(G)\)
• On 1-König-Egerváry graphs
• On almost bipartite non-König-Egerváry graphs
• New structural bounds for \(\operatorname{ker}(G)\) and \(\operatorname{core}(G)\)
• A core-corona characterization of König-Egerváry graphs
• On the intersection of all critical sets of a unicyclic graph

This page was built for publication: Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems

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