The stable set problem and the thinness of a graph

DOI10.1016/j.orl.2006.01.009zbMath1121.05113OpenAlexW2004317264MaRDI QIDQ2643810

Gianpaolo Oriolo, Federico Ricci, Carlo Mannino, 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

stable setpathwidthfrequency assignmentthinness

Mathematics Subject Classification ID

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

Related Items

Thinness of product graphs ⋮ Solving problems on generalized convex graphs via mim-width ⋮ On the thinness and proper thinness of a graph ⋮ 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 ⋮ Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem ⋮ Solving problems on generalized convex graphs via mim-width ⋮ Fixed cardinality stable sets ⋮ An \(\mathcal O(n\sqrt m)\) algorithm for the weighted stable set problem in \{claw, net\}-free graphs with \(\alpha(G)\geq 4\) ⋮ A Lagrangian heuristic for satellite range scheduling with resource constraints ⋮ On \(H\)-topological intersection graphs ⋮ Heuristic manipulation, tabu search and frequency assignment ⋮ Precedence thinness in graphs

Uses Software

• CALMA

Cites Work

• Unnamed Item
• Unnamed Item
• A survey of very large-scale neighborhood search techniques
• An optimal greedy heuristic to color interval graphs
• A unified approach to domination problems on interval graphs
• An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
• A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem.
• Efficient algorithms for interval graphs and circular-arc graphs
• Models and solution techniques for frequency assignment problems