Computing independent sets in graphs with large girth
From MaRDI portal
Publication:1183338
DOI10.1016/0166-218X(92)90041-8zbMath0769.05053MaRDI QIDQ1183338
Publication date: 28 June 1992
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (43)
Boundary classes of graphs for the dominating set problem ⋮ Complexity and Polynomially Solvable Special Cases of QUBO ⋮ New results on independent sets in extensions of \(2K_2\)-free graphs ⋮ New applications of clique separator decomposition for the maximum weight stable set problem ⋮ Edge density and independence ratio in triangle-free graphs with maximum degree three ⋮ From matchings to independent sets ⋮ Improved FPT algorithms for weighted independent set in bull-free graphs ⋮ Independent set under a change constraint from an initial solution ⋮ Astral graphs (threshold graphs), scale-free graphs and related algorithmic questions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Boundary Classes of Planar Graphs ⋮ Weighted independent sets in a subclass of \(P_6\)-free graphs ⋮ On the \(d\)-claw vertex deletion problem ⋮ Distance-\(d\) independent set problems for bipartite and chordal graphs ⋮ Stable sets in two subclasses of banner-free graphs ⋮ Unnamed Item ⋮ Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number ⋮ Stability preserving transformations of graphs ⋮ On Complexity of Total Vertex Cover on Subcubic Graphs ⋮ Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes ⋮ Randomized Greedy Algorithms for Independent Sets and Matchings in Regular Graphs: Exact Results and Finite Girth Corrections ⋮ NP-hard graph problems and boundary classes of graphs ⋮ On minimum maximal distance-\(k\) matchings ⋮ Critical hereditary graph classes: a survey ⋮ Maximum regular induced subgraphs in \(2P_3\)-free graphs ⋮ On graphs without a \(C_{4}\) or a diamond ⋮ Boundary properties of graphs for algorithmic graph problems ⋮ On the maximum independent set problem in subclasses of subcubic graphs ⋮ The Maximum Independent Set Problem in Planar Graphs ⋮ On the complexity of the independent set problem in triangle graphs ⋮ The complexity of dissociation set problems in graphs ⋮ A note on the greedy algorithm for finding independent sets of \(C_k\)-free graphs ⋮ Stable sets in \(k\)-colorable \(P_{5}\)-free graphs ⋮ Upper domination: towards a dichotomy through boundary properties ⋮ On the \(d\)-claw vertex deletion problem ⋮ Finding augmenting chains in extensions of claw-free graphs ⋮ Maximum independent sets in subcubic graphs: new results ⋮ Independent sets in \((P_4+P_4\),triangle)-free graphs ⋮ A Boundary Property for Upper Domination ⋮ Domination, coloring and stability in \(P_5\)-reducible graphs ⋮ Extending the MAX algorithm for maximum independent set ⋮ The maximum clique problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Ramsey numbers and an approximation algorithm for the vertex cover problem
- Lower bounds on the stability number of graphs computed in terms of degrees
- Some simplified NP-complete graph problems
- Lower bounds on the independence number in terms of the degrees
- Graph Theory and Probability
- Some Ramsey-Type Numbers and the Independence Ratio
- Girth and Independence Ratio
- Vertex packings: Structural properties and algorithms
- Two-Processor Scheduling with Start-Times and Deadlines
This page was built for publication: Computing independent sets in graphs with large girth
