A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH

DOI10.15807/JORSJ.44.194zbMATH Open1128.05318OpenAlexW1582786162MaRDI QIDQ4483540FDOQ4483540

Authors: Daishin Nakamura, Akihisa Tamura 

Publication date: 27 May 2003

Published in: Journal of the Operations Research Society of Japan (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.15807/jorsj.44.194

Recommendations

• An \(\mathcal{O}(m\log n)\) algorithm for the weighted stable set problem in claw-free graphs with \(\alpha ({G}) \leq 3\)
• A reduction algorithm for the weighted stable set problem in claw-free graphs
• A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs
• An \(\mathcal{O} (n^2 \log{n})\) algorithm for the weighted stable set problem in claw-free graphs
• scientific article; zbMATH DE number 1839471

Mathematics Subject Classification ID

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

Cited In (64)

• A polytime preprocess algorithm for the maximum independent set problem
• Hard and easy instances of L-tromino tilings
• An efficient local search algorithm with large neighborhoods for the maximum weighted independent set problem†
• Title not available (Why is that?)
• The limits of local search for weighted \(k\)-set packing
• On a conjecture of \textit{TxGraffiti}: relating zero forcing and vertex covers in graphs
• Packing \(K_r\)s in bounded degree graphs
• Stable sets in claw-free graphs: a journey through algorithms and polytopes
• The stable set polytope of claw-free graphs with stability number at least four. I. Fuzzy antihat graphs are \(\mathcal{W}\)-perfect
• On the recognition of fuzzy circular interval graphs
• On independent vertex sets in subclasses of apple-free graphs
• A reduction algorithm for the weighted stable set problem in claw-free graphs
• Independent sets of maximum weight in (\(p,q\))-colorable graphs.
• Coloring fuzzy circular interval graphs
• Separation routine and extended formulations for the stable set problem in claw-free graphs
• Title not available (Why is that?)
• Graphs without large apples and the maximum weight independent set problem
• Colouring squares of claw-free graphs
• Maximum regular induced subgraphs in \(2P_3\)-free graphs
• On the feedback vertex set polytope of a series-parallel graph
• The stable set problem and the thinness of a graph
• A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs
• The complexity of dissociation set problems in graphs
• An \(\mathcal O(n\sqrt m)\) algorithm for the weighted stable set problem in \{claw, net\}-free graphs with \(\alpha(G)\geq 4\)
• Robust algorithms for the stable set problem
• The limits of local search for weighted \(k\)-set packing
• New results on independent sets in extensions of \(2K_2\)-free graphs
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• Colouring squares of claw-free graphs
• Combinatorics and algorithms for augmenting graphs
• Sparse regular induced subgraphs in \(2P_3\)-free graphs
• Tight results on minimum entropy set cover
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• The stable set polytope of quasi-line graphs
• Maximum weight independent sets for (\(S_{1,2,4}\), triangle)-free graphs in polynomial time
• Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs
• On the complexity of the independent set problem in triangle graphs
• Clique-circulants and the stable set polytope of fuzzy circular interval graphs
• Independent sets in \((P_4+P_4\),triangle)-free graphs
• Integer round-up property for the chromatic number of some \(h\)-perfect graphs
• Clique family inequalities for the stable set polytope of quasi-line graphs.
• Maximum colorful independent sets in vertex-colored graphs
• On minimal prime extensions of a four-vertex graph in a prime graph
• The 0-1 inverse maximum stable set problem
• Title not available (Why is that?)
• Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
• A sufficient condition to extend polynomial results for the maximum independent set problem
• Finding augmenting chains in extensions of claw-free graphs
• Squares of Intersection Graphs and Induced Matchings
• Treewidth versus clique number. I: Graph classes with a forbidden structure
• Separating stable sets in claw-free graphs via Padberg-Rao and compact linear programs
• Minimum weighted clique cover on claw‐free perfect graphs
• 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
• Hereditary efficiently dominatable graphs
• Asymptotics of the chromatic number for quasi-line graphs
• Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs
• Maximum weight independent sets for (\(P_7\), triangle)-free graphs in polynomial time
• Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time
• Domination when the stars are out
• Penta-extensions of hereditary classes of graphs
• Minimum cost and list homomorphisms to semicomplete digraphs
• Solving the weighted stable set problem in claw-free graphs via decomposition
• On the facets of stable set polytopes of circular interval graphs
• Title not available (Why is that?)

This page was built for publication: A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4483540)