IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v21y2011i3d10.1007_s10878-009-9249-2.html
   My bibliography  Save this article

The k-coloring fitness landscape

Author

Listed:
  • Hend Bouziri

    (LARODEC-ISG, ESSEC)

  • Khaled Mellouli

    (LARODEC-ISG, IHEC)

  • El-Ghazali Talbi

    (LIFL, University of Lille 1, CNRS, INRIA)

Abstract

This paper deals with the fitness landscape analysis of the k-coloring problem. We study several standard instances extracted from the second DIMACS benchmark. Statistical indicators are used to investigate both global and local structure of fitness landscapes. An approximative distance on the k-coloring space is proposed to perform these statistical measures. Local search operator trajectories on various landscapes are then studied using the time series analysis. Results are used to better understand the behavior of metaheuristics based on local search when dealing with the graph coloring problem.

Suggested Citation

  • Hend Bouziri & Khaled Mellouli & El-Ghazali Talbi, 2011. "The k-coloring fitness landscape," Journal of Combinatorial Optimization, Springer, vol. 21(3), pages 306-329, April.
    • Handle: RePEc:spr:jcomop:v:21:y:2011:i:3:d:10.1007_s10878-009-9249-2
    DOI: 10.1007/s10878-009-9249-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-009-9249-2
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-009-9249-2?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Wim Hordijk, 1995. "A Measure of Landscapes," Working Papers 95-05-049, Santa Fe Institute.
    2. H. W. Kuhn, 1956. "Variants of the hungarian method for assignment problems," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 3(4), pages 253-258, December.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Mehran Farzadmehr & Valentin Carlan & Thierry Vanelslander, 2023. "Contemporary challenges and AI solutions in port operations: applying Gale–Shapley algorithm to find best matches," Journal of Shipping and Trade, Springer, vol. 8(1), pages 1-44, December.
    2. Wei, Wei & Feng, Xiangnan, 2023. "Graphical representation and hierarchical decomposition mechanism for vertex-cover solution space," Applied Mathematics and Computation, Elsevier, vol. 458(C).
    3. Gunter P. Wagner & Peter F. Stadler, 1997. "Complex Adaptations and the Structure of Recombination Spaces," Working Papers 97-03-029, Santa Fe Institute.
    4. Xiaojuan Ning & Yule Liu & Yishu Ma & Zhiwei Lu & Haiyan Jin & Zhenghao Shi & Yinghui Wang, 2024. "TSPconv-Net: Transformer and Sparse Convolution for 3D Instance Segmentation in Point Clouds," Mathematics, MDPI, vol. 12(18), pages 1-15, September.
    5. Ekta Jain & Kalpana Dahiya & Vanita Verma, 2020. "A priority based unbalanced time minimization assignment problem," OPSEARCH, Springer;Operational Research Society of India, vol. 57(1), pages 13-45, March.
    6. Helena Gaspars-Wieloch, 2021. "The Assignment Problem in Human Resource Project Management under Uncertainty," Risks, MDPI, vol. 9(1), pages 1-17, January.
    7. Estate V. Khmaladze, 2021. "Distribution-free testing in linear and parametric regression," Annals of the Institute of Statistical Mathematics, Springer;The Institute of Statistical Mathematics, vol. 73(6), pages 1063-1087, December.
    8. Subbiah Baskaran & Peter F. Stadler & Peter Schuster, 1995. "Approximate Scaling Properties of RNA Free Energy Landscapes," Working Papers 95-10-083, Santa Fe Institute.
    9. Ivan Belik & Kurt Jornsten, 2018. "Critical objective function values in linear sum assignment problems," Journal of Combinatorial Optimization, Springer, vol. 35(3), pages 842-852, April.
    10. Amnon Rosenmann, 2022. "Computing the sequence of k-cardinality assignments," Journal of Combinatorial Optimization, Springer, vol. 44(2), pages 1265-1283, September.
    11. Peter F. Stadler & Gunjter P. Wagner, 1996. "The Algebraic Theory of Recombination Spaces," Working Papers 96-07-046, Santa Fe Institute.
    12. Li, Miao & Davari, Morteza & Goossens, Dries, 2023. "Multi-league sports scheduling with different leagues sizes," European Journal of Operational Research, Elsevier, vol. 307(1), pages 313-327.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:21:y:2011:i:3:d:10.1007_s10878-009-9249-2. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.