Polynomial algorithm for finding the largest independent sets in graphs without forks

DOI10.1016/S0166-218X(02)00290-1zbMath0931.05078OpenAlexW2015564725MaRDI QIDQ4936659

Publication date: 31 January 2000

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(02)00290-1

zbMATH Keywords

algorithm independent set

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (69)

Polynomial-time approximation algorithms for the coloring problem in some cases ⋮ Solving Problems on Graphs of High Rank-Width ⋮ The Maximum Weight Stable Set Problem in ( $$P_6$$ , bull)-Free Graphs ⋮ The maximum independent set problem in subclasses of $S_{i, j, k}$-free graphs ⋮ Some observations on maximum weight stable sets in certain $P_{5}$-free graphs ⋮ A complexity dichotomy and a new boundary class for the dominating set problem ⋮ Independent sets in graphs without subtrees with many leaves ⋮ New Cases of the Polynomial Solvability of the Independent Set Problem for Graphs with Forbidden Paths ⋮ A sufficient condition to extend polynomial results for the maximum independent set problem ⋮ New results on independent sets in extensions of $2K_2$-free graphs ⋮ Coloring graph classes with no induced fork via perfect divisibility ⋮ Partitioning $H$-free graphs of bounded diameter ⋮ New applications of clique separator decomposition for the maximum weight stable set problem ⋮ From matchings to independent sets ⋮ A subexponential-time algorithm for the maximum independent set problem in $P_t$-free graphs ⋮ On the number of boundary classes in the 3-colouring problem ⋮ An efficient local search algorithm with large neighborhoods for the maximum weighted independent set problem† ⋮ (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth ⋮ Maximum weight independent sets for ($P_7$,triangle)-free graphs in polynomial time ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Maximum weight independent set for $\ell$claw-free graphs in polynomial time ⋮ Stability number of bull- and chair-free graphs revisited ⋮ Classes of perfect graphs ⋮ An augmenting graph approach to the stable set problem in $P_{5}$-free graphs ⋮ On easy and hard hereditary classes of graphs with respect to the independent set problem ⋮ Struction revisited ⋮ On the structure and stability number of $P_{5}$- and co-chair-free graphs ⋮ $P_{5}$-free augmenting graphs and the maximum stable set problem ⋮ Stable sets in two subclasses of banner-free graphs ⋮ Some results on maximum stable sets in certain $P_{5}$-free graphs ⋮ Solving problems on graphs of high rank-width ⋮ Unnamed Item ⋮ Subexponential-time algorithms for maximum independent set in $P_t$-free and broom-free graphs ⋮ Boundary properties of the satisfiability problems ⋮ Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes ⋮ Stable sets of maximum weight in ($P_{7}$, banner)-free graphs ⋮ Critical hereditary graph classes: a survey ⋮ On finding augmenting graphs ⋮ A polynomial algorithm to find an independent set of maximum weight in a fork-free graph ⋮ Maximum regular induced subgraphs in $2P_3$-free graphs ⋮ Independent sets in extensions of 2$K_{2}$-free graphs ⋮ Augmenting graphs for independent sets ⋮ Augmenting chains in graphs without a skew star. ⋮ Maximum independent sets in subclasses of $P_{5}$-free graphs ⋮ Some new hereditary classes where graph coloring remains NP-hard ⋮ Few induced disjoint paths for $H$-free graphs ⋮ Counting independent sets in graphs with bounded bipartite pathwidth ⋮ 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 ⋮ Connected vertex cover for $(sP_1+P_5)$-free graphs ⋮ A new distributed approximation algorithm for the maximum weight independent set problem ⋮ Maximum weight independent sets for ($S_{1,2,4}$,triangle)-free graphs in polynomial time ⋮ Finding augmenting chains in extensions of claw-free graphs ⋮ Graphs without large apples and the maximum weight independent set problem ⋮ Independent sets in $(P_4+P_4$,triangle)-free graphs ⋮ Excluding the fork and antifork ⋮ Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes ⋮ Large independent sets in random regular graphs ⋮ Chordal bipartite graphs of bounded tree- and clique-width ⋮ Few induced disjoint paths for $H$-free graphs ⋮ Extending the MAX algorithm for maximum independent set ⋮ New sufficient conditions for $\alpha$-redundant vertices ⋮ The maximum independent set problem in subclasses of subcubic graphs ⋮ Squares of Intersection Graphs and Induced Matchings ⋮ On the stable set problem in special $P_{5}$-free graphs ⋮ Penta-extensions of hereditary classes of graphs ⋮ Vertex cover at distance on $H$-free graphs

Cites Work

This page was built for publication: Polynomial algorithm for finding the largest independent sets in graphs without forks