Polynomial algorithm for finding the largest independent sets in graphs without forks
From MaRDI portal
Recommendations
- A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
- On locally optimal independent sets and vertex covers
- Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs
- Maximum weight independent set for claw-free graphs in polynomial time
- Square-free graphs with no induced fork
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 468640 (Why is no real title available?)
- A New Algorithm for Generating All the Maximal Independent Sets
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- Matching theory
- On maximal independent sets of vertices in claw-free graphs
- Stability number of bull- and chair-free graphs
Cited in
(79)- A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs
- scientific article; zbMATH DE number 7651162 (Why is no real title available?)
- Few induced disjoint paths for \(H\)-free graphs
- Few induced disjoint paths for \(H\)-free graphs
- Connected vertex cover for \((sP_1+P_5)\)-free graphs
- Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems
- Extending the MAX algorithm for maximum independent set
- Graphs without large apples and the maximum weight independent set problem
- Complete complexity dichotomies for the dominating set problem
- scientific article; zbMATH DE number 7651174 (Why is no real title available?)
- Maximum regular induced subgraphs in 2P₃-free graphs
- The Maximum Independent Set Problem in Planar Graphs
- Vertex cover at distance on \(H\)-free graphs
- The maximum weight stable set problem in (\(P_6\), bull)-free graphs
- Independent set reconfiguration in H-free graphs
- The maximum independent set problem in subclasses of \(S_{i, j, k}\)-free graphs
- New cases of the polynomial solvability of the independent set problem for graphs with forbidden paths
- Struction revisited
- Polynomial-time approximation algorithms for the coloring problem in some cases
- Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes
- Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs
- The complexity of dissociation set problems in graphs
- On the stable set problem in special \(P_{5}\)-free graphs
- scientific article; zbMATH DE number 7742928 (Why is no real title available?)
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- An efficient local search algorithm with large neighborhoods for the maximum weighted independent set problem†
- On finding augmenting graphs
- New results on independent sets in extensions of \(2K_2\)-free graphs
- Augmenting chains in graphs without a skew star.
- Independent sets in extensions of 2\(K_{2}\)-free graphs
- From matchings to independent sets
- On the number of boundary classes in the 3-colouring problem
- Excluding the fork and antifork
- New applications of clique separator decomposition for the maximum weight stable set problem
- A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
- (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth
- Critical hereditary graph classes: a survey
- Maximum weight independent sets for (\(S_{1,2,4}\), triangle)-free graphs in polynomial time
- A complexity dichotomy and a new boundary class for the dominating set problem
- Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs
- On the complexity of the independent set problem in triangle graphs
- Independent sets in \((P_4+P_4\),triangle)-free graphs
- Independent transversals versus transversals
- Coloring graph classes with no induced fork via perfect divisibility
- On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
- Stable sets in two subclasses of banner-free graphs
- Boundary properties of the satisfiability problems
- On distance-d independent set problems for some graph classes
- Solving problems on graphs of high rank-width
- An algorithm for calculating the independence and vertex-cover polynomials of a graph
- Partitioning \(H\)-free graphs of bounded diameter
- Classes of perfect graphs
- A sufficient condition to extend polynomial results for the maximum independent set problem
- Finding augmenting chains in extensions of claw-free graphs
- Maximum independent sets in subclasses of \(P_{5}\)-free graphs
- Large independent sets in random regular graphs
- Chordal bipartite graphs of bounded tree- and clique-width
- The maximum independent set problem in subclasses of subcubic graphs
- Some new hereditary classes where graph coloring remains NP-hard
- Glauber dynamics for the hard-core model on bounded-degree H-free graphs
- Maximum independent set when excluding an induced minor: K₁ + tK₂ and tC₃ C₄
- Parameterized algorithms for the independent set problem in some hereditary graph classes
- Squares of Intersection Graphs and Induced Matchings
- \(P_{5}\)-free augmenting graphs and the maximum stable set problem
- An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs
- Independent sets in graphs without subtrees with many leaves
- Max weight independent set in sparse graphs with no long claws
- Augmenting graphs for independent sets
- Maximum weight independent sets for (\(P_7\), triangle)-free graphs in polynomial time
- Counting independent sets in graphs with bounded bipartite pathwidth
- Maximum weight independent set for claw-free graphs in polynomial time
- Stability number of bull- and chair-free graphs revisited
- A polynomial Turing-kernel for weighted independent set in bull-free graphs
- Solving problems on graphs of high rank-width
- Some results on maximum stable sets in certain \(P_{5}\)-free graphs
- Penta-extensions of hereditary classes of graphs
- Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs
- A new distributed approximation algorithm for the maximum weight independent set problem
- New sufficient conditions for \(\alpha\)-redundant vertices
This page was built for publication: Polynomial algorithm for finding the largest independent sets in graphs without forks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4936659)
