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