New results on independent sets in extensions of $2K_2$-free graphs

DOI10.1007/s00373-022-02532-9zbMath1494.05088OpenAlexW4288701827MaRDI QIDQ2159731

Publication date: 2 August 2022

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-022-02532-9

zbMATH Keywords

polynomial algorithms maximum independent set problem hereditary graph classes $2K_2$-free graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Dynamic programming (90C39) Structural characterization of families of graphs (05C75) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
A sufficient condition to extend polynomial results for the maximum independent set problem
Maximum regular induced subgraphs in $2P_3$-free graphs
Maximum independent sets in subclasses of $P_{5}$-free graphs
On diameters and radii of bridged graphs
On maximal independent sets of vertices in claw-free graphs
Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
Computing independent sets in graphs with large girth
Some simplified NP-complete graph problems
On easy and hard hereditary classes of graphs with respect to the independent set problem
Maximum weight independent set for $\ell$claw-free graphs in polynomial time
Subexponential-time algorithms for maximum independent set in $P_t$-free and broom-free graphs
An $\mathcal O(n\sqrt m)$ algorithm for the weighted stable set problem in \{claw, net\}-free graphs with $\alpha(G)\geq 4$
Independent sets in extensions of 2$K_{2}$-free graphs
Sparse regular induced subgraphs in $2P_3$-free graphs
Maximum weight independent sets in ($P_6$, co-banner)-free graphs
An $\mathcal{O} (n^2 \log{n})$ algorithm for the weighted stable set problem in claw-free graphs
An $\mathcal{O}(m\log n)$ algorithm for the weighted stable set problem in claw-free graphs with $\alpha ({G}) \leq 3$
From matchings to independent sets
A subexponential-time algorithm for the maximum independent set problem in $P_t$-free graphs
Combinatorics and algorithms for augmenting graphs
A Linear Recognition Algorithm for Cographs
A New Algorithm for Generating All the Maximal Independent Sets
The Rectilinear Steiner Tree Problem is $NP$-Complete
Graph Classes: A Survey
A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
Independence and Efficient Domination on P ₆ -free Graphs
Polynomial algorithm for finding the largest independent sets in graphs without forks
Reducibility among Combinatorial Problems
Polynomial-time algorithm for Maximum Weight Independent Set on P₆-free graphs
An upper bound on the number of cliques in a graph
Independent Set in P₅-Free Graphs in Polynomial Time
Independent Sets of Maximum Weight in Apple-Free Graphs
Independent Sets of Maximum Weight in Apple-Free Graphs
A polynomial algorithm to find an independent set of maximum weight in a fork-free graph

This page was built for publication: New results on independent sets in extensions of $2K_2$-free graphs

New results on independent sets in extensions of \(2K_2\)-free graphs