Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
From MaRDI portal
Publication:1144589
DOI10.1016/0012-365X(90)90287-RzbMath0444.05049WikidataQ56335613 ScholiaQ56335613MaRDI QIDQ1144589
Publication date: 1980
Published in: Discrete Mathematics (Search for Journal in Brave)
Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)
Related Items (only showing first 100 items - show all)
On claw-free asteroidal triple-free graphs ⋮ Edge-disjoint packings of graphs ⋮ Independent sets of maximum weight in (\(p,q\))-colorable graphs. ⋮ Quelques utilisations de la STRUCTION. (Some applications of STRUCTION) ⋮ On the vertex packing problem ⋮ Augmenting approach for some maximum set problems ⋮ Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs ⋮ On the feedback vertex set polytope of a series-parallel graph ⋮ Enumeration of maximal irredundant sets for claw-free graphs ⋮ Polynomially solvable cases for the maximum stable set problem ⋮ The maximum independent set problem in subclasses of \(S_{i, j, k}\)-free graphs ⋮ Well-covered triangulations. IV ⋮ Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs ⋮ Claw-free graphs---a survey ⋮ Matching extension in \(K_{1,r}\)-free graphs with independent claw centers ⋮ A nice class for the vertex packing problem ⋮ On the use of Boolean methods for the computation of the stability number ⋮ 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 ⋮ The limits of local search for weighted \(k\)-set packing ⋮ Partitioning \(H\)-free graphs of bounded diameter ⋮ New applications of clique separator decomposition for the maximum weight stable set problem ⋮ Boundary classes for graph problems involving non-local properties ⋮ Claw-free strictly Deza graphs ⋮ From matchings to independent sets ⋮ Dominating sets and Hamiltonicity in \(K_{1,3}\)-free graphs ⋮ Independent sets in some classes of \(S_{i,j,k}\)-free graphs ⋮ A note on anti-coordination and social interactions ⋮ Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity ⋮ Reconfiguration in bounded bandwidth and tree-depth ⋮ On maximal independent sets of vertices in claw-free graphs ⋮ Colouring squares of claw-free graphs ⋮ On the structure of 4-regular planar well-covered graphs ⋮ Independent domination in finitely defined classes of graphs ⋮ Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time ⋮ Scalar aggregation in inconsistent databases. ⋮ Polytope des independants d'un graphe série-parallèle ⋮ Independence systems with continuous cardinality of bases ⋮ 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 ⋮ On well-covered triangulations. I ⋮ \(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 ⋮ Clique family inequalities for the stable set polytope of quasi-line graphs. ⋮ Algorithms for minimum covering by cliques and maximum clique in claw- free perfect graphs ⋮ Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs ⋮ Dominating set is fixed parameter tractable in claw-free graphs ⋮ Induced matchings in intersection graphs. ⋮ Stabex method for extension of \(\alpha\)-polynomial hereditary classes. ⋮ A note on graphs contraction-critical with respect to independence number ⋮ Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs ⋮ On the maximum acyclic subgraph problem under disjunctive constraints ⋮ Independent feedback vertex set for \(P_5\)-free graphs ⋮ Clique-circulants and the stable set polytope of fuzzy circular interval graphs ⋮ The stable set polytope of quasi-line graphs ⋮ On finding augmenting graphs ⋮ Correction to: ``A connection between sports and matroids: how many teams can we beat? ⋮ On well-covered pentagonalizations of the plane ⋮ Maximum regular induced subgraphs in \(2P_3\)-free graphs ⋮ Stability number of bull- and chair-free graphs ⋮ On well-covered triangulations. II. ⋮ Independent sets in extensions of 2\(K_{2}\)-free graphs ⋮ On well-covered triangulations. III ⋮ Augmenting graphs for independent sets ⋮ Augmenting chains in graphs without a skew star. ⋮ Maximum independent sets in subclasses of \(P_{5}\)-free graphs ⋮ On the complexity of the independent set problem in triangle graphs ⋮ The complexity of dissociation set problems in graphs ⋮ Maximum independent sets near the upper bound ⋮ Sparse regular induced subgraphs in \(2P_3\)-free graphs ⋮ Maximum weight independent sets for (\(S_{1,2,4}\),triangle)-free graphs in polynomial time ⋮ Finding augmenting chains in extensions of claw-free graphs ⋮ Independent sets in \((P_4+P_4\),triangle)-free graphs ⋮ Cycles of given length in some \(K_{1,3}\)-free graphs ⋮ TABARIS: An exact algorithm based on tabu search for finding a maximum independent set in a graph ⋮ Stability in CAN-free graphs ⋮ Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes ⋮ Counting edge-injective homomorphisms and matchings on restricted graph classes ⋮ Some classical combinatorial problems on circulant and claw-free graphs: The isomorphism and coloring problems on circulant graphs and the stable set problem on claw-free graphs ⋮ Stability in \(P_5\)- and banner-free graphs ⋮ Recent trends in combinatorial optimization ⋮ Stable sets in certain \(P_6\)-free graphs ⋮ Few induced disjoint paths for \(H\)-free graphs ⋮ Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time. ⋮ 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 ⋮ The struction of a graph: Application to CN-free graphs ⋮ The maximum clique problem ⋮ Penta-extensions of hereditary classes of graphs ⋮ The \(k\)-separator problem: polyhedra, complexity and approximation results ⋮ Extending matchings in graphs: A survey ⋮ Extending matchings in claw-free graphs ⋮ Vertex cover at distance on \(H\)-free graphs ⋮ The complexity of generalized clique packing ⋮ Regular independent sets
Cites Work
This page was built for publication: Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
