A polynomial algorithm to find an independent set of maximum weight in a fork-free graph

DOI10.1016/j.jda.2008.04.001zbMath1154.90607OpenAlexW2100432797MaRDI QIDQ5901434

Publication date: 23 February 2009

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2008.04.001

zbMATH Keywords

independent set polynomial-time algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (54)

A characterization of claw-free CIS graphs and new results on the order of CIS graphs ⋮ Weighted independent sets in classes of $P_6$-free graphs ⋮ The Maximum Weight Stable Set Problem in ( $$P_6$$ , bull)-Free Graphs ⋮ Tent and a subclass of $P_{5}$-free graphs ⋮ Structure of squares and efficient domination in graph classes ⋮ Maximum weight independent sets in classes related to claw-free graphs ⋮ 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 ⋮ From matchings to independent sets ⋮ Independent sets in some classes of $S_{i,j,k}$-free graphs ⋮ On atomic structure of $P_5$-free subclasses and maximum weight independent set problem ⋮ Combining decomposition approaches for the maximum weight stable 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 ⋮ Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs ⋮ Maximum weight t-sparse set problem on vector-weighted graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Computing well-covered vector spaces of graphs using modular decomposition ⋮ Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in $\boldsymbol{H}$-Free Graphs ⋮ Maximum weight independent set for $\ell$claw-free graphs in polynomial time ⋮ Weighted independent sets in a subclass of $P_6$-free graphs ⋮ Weighted efficient domination in two subclasses of $P_6$-free graphs ⋮ Distance-$d$ independent set problems for bipartite and chordal graphs ⋮ Maximum weight stable set in ($P_7$, bull)-free graphs and ($S_{1, 2, 3}$, bull)-free graphs ⋮ Hybrid tractability of valued constraint problems ⋮ Complexity results for equistable graphs and related classes ⋮ Approximation Algorithm for the Distance-3 Independent Set Problem on Cubic Graphs ⋮ A note on efficient domination in a superclass of $P_5$-free graphs ⋮ Dominating induced matchings in graphs without a skew star ⋮ Subexponential-time algorithms for maximum independent set in $P_t$-free and broom-free graphs ⋮ Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs ⋮ Covering minimal separators and potential maximal cliques in $P_t$-free graphs ⋮ Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes ⋮ Maximum regular induced subgraphs in $2P_3$-free graphs ⋮ Approximation of knapsack problems with conflict and forcing graphs ⋮ On the maximum independent set problem in subclasses of subcubic graphs ⋮ Maximum weight independent sets in hole- and dart-free graphs ⋮ On the complexity of the independent set problem in triangle graphs ⋮ The complexity of dissociation set problems in graphs ⋮ Independent Sets in Classes Related to Chair-Free Graphs ⋮ Sparse regular induced subgraphs in $2P_3$-free graphs ⋮ Subexponential-time algorithms for finding large induced sparse subgraphs ⋮ Maximum weight independent sets for ($S_{1,2,4}$,triangle)-free graphs in polynomial time ⋮ Graphs without large apples and the maximum weight independent set problem ⋮ Maximum independent sets in subcubic graphs: new results ⋮ Parameterized inapproximability of independent set in $H$-free graphs ⋮ Independent sets in $(P_4+P_4$,triangle)-free graphs ⋮ Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs ⋮ Excluding the fork and antifork ⋮ Counting Weighted Independent Sets beyond the Permanent ⋮ Squares of Intersection Graphs and Induced Matchings ⋮ The $k$-separator problem: polyhedra, complexity and approximation results

Cites Work

This page was built for publication: A polynomial algorithm to find an independent set of maximum weight in a fork-free graph