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
Enumeration of Maximal Irredundant Sets for Claw-Free Graphs, Combinatorics and algorithms for augmenting graphs, Independent sets in graphs without subtrees with many leaves, WELL-COVERED GRAPHS: A SURVEY, On the complexity of colouring antiprismatic graphs, On weights of induced paths and cycles in claw-free andK1,r-free graphs, A Note on the Minimum H-Subgraph Edge Deletion, On the facets of stable set polytopes of circular interval graphs, Induced disjoint paths and connected subgraphs for \(H\)-free graphs, Induced disjoint paths and connected subgraphs for \(H\)-free graphs, A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs, Domination number and feedback vertex number of complements of line graphs, Counterexamples to the characterisation of graphs with equal independence and annihilation number, A polytime preprocess algorithm for the maximum independent set problem, Efficiently recognizing graphs with equal independence and annihilation numbers, Unnamed Item, Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs, Lovász-Schrijver PSD-operator and the stable set polytope of claw-free graphs, Unnamed Item, Colouring Squares of Claw-free Graphs, Approximating Incremental Combinatorial Optimization Problems, A Polynomial Kernel for Line Graph Deletion, Domination When the Stars Are Out, Hard graphs for the maximum clique problem, A polynomial algorithm to find an independent set of maximum weight in a fork-free graph, Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes, On a classification of independence systems, On Some Properties of the Struction of a Graph, Polynomial algorithm for finding the largest independent sets in graphs without forks, Few induced disjoint paths for \(H\)-free graphs, The Maximum Independent Set Problem in Planar Graphs, On the relation of strong triadic closure and cluster deletion, Connected vertex cover for \((sP_1+P_5)\)-free graphs, Independent Sets in Classes Related to Chair-Free Graphs, On cycle transversals and their connected variants in the absence of a small linear forest, A survey on graphs with convex quadratic stability number, Computing subset transversals in \(H\)-free graphs, Parameterized inapproximability of independent set in \(H\)-free graphs, Hard and easy instances of L-tromino tilings, Independent Set Reconfiguration in Cographs and their Generalizations, Unnamed Item, Lovász-Schrijver PSD-Operator on Claw-Free Graphs, Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition, On balanced graphs, 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
