Computing independent sets in graphs with large girth

Recommendations

Finding Large Independent Sets in Graphs and Hypergraphs
Large independent sets in regular graphs of large girth
Computing \(k\)-independent sets for regular bipartite graphs
Approximating independent sets in sparse graphs
scientific article; zbMATH DE number 1182757
Computing the numbers of independent sets and matchings of all sizes for graphs with bounded treewidth
Large independent sets in shift-invariant graphs
scientific article; zbMATH DE number 4049676
scientific article; zbMATH DE number 1305487
Computing maximum independent set on outerstring graphs and their relatives

Cites work

scientific article; zbMATH DE number 3675940 (Why is no real title available?)
scientific article; zbMATH DE number 3598475 (Why is no real title available?)
scientific article; zbMATH DE number 3445275 (Why is no real title available?)
Girth and Independence Ratio
Graph Theory and Probability
Lower bounds on the independence number in terms of the degrees
Lower bounds on the stability number of graphs computed in terms of degrees
Ramsey numbers and an approximation algorithm for the vertex cover problem
Some Ramsey-Type Numbers and the Independence Ratio
Some simplified NP-complete graph problems
Two-Processor Scheduling with Start-Times and Deadlines
Vertex packings: Structural properties and algorithms

Cited in

(54)

Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
Computing maximum independent set on outerstring graphs and their relatives
scientific article; zbMATH DE number 7651162 (Why is no real title available?)
Computing \(k\)-independent sets for regular bipartite graphs
scientific article; zbMATH DE number 7742925 (Why is no real title available?)
The maximum clique problem
Extending the MAX algorithm for maximum independent set
Boundary properties of graphs for algorithmic graph problems
On relating edges in graphs without cycles of length 4
On graphs without a \(C_{4}\) or a diamond
Maximum regular induced subgraphs in 2P₃-free graphs
The Maximum Independent Set Problem in Planar Graphs
Astral graphs (threshold graphs), scale-free graphs and related algorithmic questions
Improved FPT algorithms for weighted independent set in bull-free graphs
On the complexity of list \(\mathcal{H}\)-packing for sparse graph classes
Domination, coloring and stability in \(P_5\)-reducible graphs
Boundary Classes of Planar Graphs
A note on the greedy algorithm for finding independent sets of \(C_k\)-free graphs
Distance-\(d\) independent set problems for bipartite and chordal graphs
The complexity of dissociation set problems in graphs
On the complexity of approximating the independent set problem (extended abstract)
Stable sets in \(k\)-colorable \(P_{5}\)-free graphs
Upper domination: towards a dichotomy through boundary properties
New results on independent sets in extensions of \(2K_2\)-free graphs
Complexity and polynomially solvable special cases of QUBO
From matchings to independent sets
On complexity of total vertex cover on subcubic graphs
Randomized greedy algorithms for independent sets and matchings in regular graphs: exact results and finite girth corrections
Boundary classes of graphs for the dominating set problem
Independent set under a change constraint from an initial solution
New applications of clique separator decomposition for the maximum weight stable set problem
Stability preserving transformations of graphs
Weighted independent sets in a subclass of P₆-free graphs
The impact of the growth rate of the packing number of graphs on the computational complexity of the independent set problem
Critical hereditary graph classes: a survey
On the complexity of the independent set problem in triangle graphs
Independent sets in \((P_4+P_4\),triangle)-free graphs
A boundary property for upper domination
Stable sets in two subclasses of banner-free graphs
NP-hard graph problems and boundary classes of graphs
On the maximum independent set problem in subclasses of subcubic graphs
scientific article; zbMATH DE number 7650083 (Why is no real title available?)
scientific article; zbMATH DE number 6180530 (Why is no real title available?)
Finding augmenting chains in extensions of claw-free graphs
Parameterized algorithms for the independent set problem in some hereditary graph classes
Complexity of the (Connected) Cluster Vertex Deletion Problem on H-free Graphs
Independent sets in the graphs with bounded minors of the extended incidence matrix
Edge density and independence ratio in triangle-free graphs with maximum degree three
On the \(d\)-claw vertex deletion problem
On minimum maximal distance-\(k\) matchings
On the \(d\)-claw vertex deletion problem
Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs
Fourier analysis and large independent sets in powers of complete graphs
Large independent sets in regular graphs of large girth

This page was built for publication: Computing independent sets in graphs with large girth

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