The stable set problem and the thinness of a graph

DOI10.1016/J.ORL.2006.01.009MaRDI QIDQ2643810zbMATH OpenOpenAlexFDO

Authors Carlo Mannino, Gianpaolo Oriolo, Federico Ricci, L. Sunil Chandran

Publication date 27 August 2007

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2108/12084

zbMATH Keywords

frequency assignmentpathwidthstable setthinness

Mathematics Subject Classification ID

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

Recommendations

• An \(\mathcal{O}(m\log n)\) algorithm for the weighted stable set problem in claw-free graphs with \(\alpha ({G}) \leq 3\)
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs
• An exact algorithm for the maximum stable set problem
• Robust algorithms for the stable set problem

Cites work

• A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem.
• A survey of very large-scale neighborhood search techniques
• A unified approach to domination problems on interval graphs
• An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
• An optimal greedy heuristic to color interval graphs
• Efficient algorithms for interval graphs and circular-arc graphs
• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• Models and solution techniques for frequency assignment problems

Cited in

(29)

• Heuristic manipulation, tabu search and frequency assignment
• An \(\mathcal O(n\sqrt m)\) algorithm for the weighted stable set problem in \{claw, net\}-free graphs with \(\alpha(G)\geq 4\)
• Fixed cardinality stable sets
• Precedence thinness in graphs
• On the thinness and proper thinness of a graph
• The stable set problem: clique and nodal inequalities revisited
• The number of all stable sets in some classes of graphs
• THE GENERALIZED STABLE SET PROBLEM FOR PERFECT BIDIRECTED GRAPHS
• scientific article; zbMATH DE number 1766756 (Why is no real title available?)
• On \(H\)-topological intersection graphs
• Twin-width and transductions of proper k-mixed-thin graphs
• Fair allocation algorithms for indivisible items under structured conflict constraints
• Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs
• Multi-neighborhood simulated annealing for the minimum interference frequency assignment problem
• A polytime preprocess algorithm for the maximum independent set problem
• On the thinness of trees
• Solving problems on generalized convex graphs via mim-width
• Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem
• Knapsack: connectedness, path, and shortest-path
• Thinness and its variations on some graph families and coloring graphs of bounded thinness
• Twin-width and transductions of proper \(k\)-mixed-thin graphs
• The simultaneous interval number: a new width parameter that measures the similarity to interval graphs
• Graph thinness: a lower bound and complexity
• On the thinness of trees
• A Lagrangian heuristic for satellite range scheduling with resource constraints
• Knapsack with vertex cover, set cover, and hitting set
• Non-crossing H-graphs: a generalization of proper interval graphs admitting FPT algorithms
• Thinness of product graphs
• Solving problems on generalized convex graphs via mim-width

Describes a project that uses

Uses Software

• CALMA

This page was built for publication: The stable set problem and the thinness of a graph

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