IDEAS home Printed from https://ideas.repec.org/a/wsi/apjorx/v30y2013i05ns0217595913500188.html
   My bibliography  Save this article

An Extraction And Expansion Approach For Graph Coloring

Author

Listed:
  • QINGHUA WU

    (School of Management, Huazhong University of Science and Technology, No. 1037, Luoyu Road, Wuhan, China;
    LERIA, Université, Université d'Angers, 2 Boulevard Lavoisier, 49045 Angers Cedex 01, France)

  • JIN-KAO HAO

    (LERIA, Université, Université d'Angers, 2 Boulevard Lavoisier, 49045 Angers Cedex 01, France)

Abstract

This paper presents an extraction and expansion approach for the graph coloring problem. The extraction phase transforms a large graph into a sequence of progressively smaller graphs by removing large independent sets from the graph. The expansion phase starts by generating an approximate coloring for the smallest graph in the sequence. Then it expands the smallest graph by progressively adding back the extracted independent sets and determine a coloring for each intermediate graph. To color each graph, a simple perturbation based tabu search algorithm is used. The proposed approach is evaluated on the DIMACS challenge benchmarks showing competitive results in comparison with the state-of-the-art methods.

Suggested Citation

  • Qinghua Wu & Jin-Kao Hao, 2013. "An Extraction And Expansion Approach For Graph Coloring," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 30(05), pages 1-18.
    • Handle: RePEc:wsi:apjorx:v:30:y:2013:i:05:n:s0217595913500188
    DOI: 10.1142/S0217595913500188
    as

    Download full text from publisher

    File URL: http://www.worldscientific.com/doi/abs/10.1142/S0217595913500188
    Download Restriction: Access to full text is restricted to subscribers
    File URL: https://libkey.io/10.1142/S0217595913500188?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. Singleton, Grant R. & Belmain, Steve R. & Brown, Peter R. & Hardy, Bill (ed.), 2010. "Rodent Outbreaks: Ecology and Impacts," IRRI Books, International Rice Research Institute (IRRI), number 164492.
    2. Okada, Akira, 2010. "Toshiji Kawagoe, Experimental Economics," Economic Review, Hitotsubashi University, vol. 61(1), pages 85-87, January.
    3. Walter S. L. Fung & Richard Y. K. Fung, 2010. "Knowledge Security For Hospitality Industry," World Scientific Book Chapters, in: Damianos P Sakas & Nikolaos Konstantopoulos (ed.), Marketing And Management Sciences, chapter 53, pages 305-308, World Scientific Publishing Co. Pte. Ltd..
    4. AfDB AfDB, 2010. "Working Paper Series – Author Guidelines," Working Paper Series 357, African Development Bank.
    5. Krіvoruchko О. & Pіpenko I., 2010. "Analysis of enterprise marketing potential," Экономика транспортного комплекса, CyberLeninka;Харьковский национальный автомобильно-дорожный университет, issue 16, pages 90-100.
    6. ., 2010. "Korea's Trade Policy in Transition," Chapters, in: The Korean Economy in Transition, chapter 5, Edward Elgar Publishing.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Alex Gliesch & Marcus Ritt, 2022. "A new heuristic for finding verifiable k-vertex-critical subgraphs," Journal of Heuristics, Springer, vol. 28(1), pages 61-91, February.

    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. Eichengreen, Barry & Flandreau, Marc & Mehl, Arnaud & Chitu, Livia, 2017. "International Currencies Past, Present, and Future: Two Views from Economic History," OUP Catalogue, Oxford University Press, number 9780190659455.
    2. Oulay Phadouangdeth & Sounthone Phommason & Phouphet Kyophilavong & Inpaeng Sayvaya, 2014. "Does the Accession of Road Reduce the Poverty? Evidence from Northern, Central, and Southern Parts of Lao PDR," International Journal of Economics and Empirical Research (IJEER), The Economics and Social Development Organization (TESDO), vol. 2(9), pages 377-386, September.
    3. Chen, Li-Ju & Hu, Shih-Wen & Wang, Vey & Wen, Jiandong & Ye, Chusheng, 2014. "The effects of purchasing and price subsidy policies for agricultural products under target zones," Economic Modelling, Elsevier, vol. 43(C), pages 439-447.
    4. Steffen Schuldenzucker & Sven Seuken & Stefano Battiston, 2017. "The Computational Complexity of Financial Networks with Credit Default Swaps," Papers 1710.01578, arXiv.org, revised May 2019.
    5. Catherine Tucker & Juanjuan Zhang, 2011. "How Does Popularity Information Affect Choices? A Field Experiment," Management Science, INFORMS, vol. 57(5), pages 828-842, May.
    6. Christina Grundström & Roland Sjöström & Anders Uddenberg & Anna Öhrwall Rönnbäck, 2012. "FAST-GROWING SMEs AND THE ROLE OF INNOVATION," International Journal of Innovation Management (ijim), World Scientific Publishing Co. Pte. Ltd., vol. 16(03), pages 1-19.
    7. Plassmann, Florenz & Feltenstein, Andrew, 2016. "How large do multi-region models need to be?," Journal of Policy Modeling, Elsevier, vol. 38(1), pages 138-155.
    8. William Peterman, 2016. "The effect of endogenous human capital accumulation on optimal taxation," Review of Economic Dynamics, Elsevier for the Society for Economic Dynamics, vol. 21, pages 46-71, July.
    9. Jayati Sarkar & Subrata Sarkar, 2018. "Bank Ownership, Board Characteristics and Performance: Evidence from Commercial Banks in India," IJFS, MDPI, vol. 6(1), pages 1-30, February.
    10. Ferri, Giovanni & Murro, Pierluigi & Peruzzi, Valentina & Rotondi, Zeno, 2019. "Bank lending technologies and credit availability in Europe: What can we learn from the crisis?," Journal of International Money and Finance, Elsevier, vol. 95(C), pages 128-148.
    11. Feng, Xiaobing & Jo, Woo Seong & Kim, Beom Jun, 2014. "International transmission of shocks and fragility of a bank network," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 403(C), pages 120-129.
    12. Scott A. Beaulier & Franklin G. Mixon & Richard J. Cebula, 2014. "Can't see the tacking for the trees? Try a Coasian solution," Chapters, in: Franklin G. Mixon & Richard J. Cebula (ed.), New Developments in Economic Education, chapter 11, pages 126-132, Edward Elgar Publishing.
    13. Daniel Titelman, 2012. "Hacia una cobertura regional más amplia de un Fondo de Reservas," Papers and Proceedings 11861, Fondo Latino Americano de Reservas - FLAR.
    14. Karásek, Jiří & Pavlica, Jaroslav, 2016. "Green Investment Scheme: Experience and results in the Czech Republic," Energy Policy, Elsevier, vol. 90(C), pages 121-130.
    15. Monica Martinez-Bravo & Gerard Padró i Miquel & Nancy Qian & Yang Yao, 2011. "Do Local Elections in Non-Democracies Increase Accountability? Evidence from Rural China," NBER Working Papers 16948, National Bureau of Economic Research, Inc.
    16. R. Alexander Bentley & Paul Ormerod, 2012. "Accelerated Innovation And Increased Spatial Diversity Of Us Popular Culture," Advances in Complex Systems (ACS), World Scientific Publishing Co. Pte. Ltd., vol. 15(01n02), pages 1-13.
    17. YANSONG HU & DAMIEN McLOUGHLIN, 2012. "Managing Quality And Network Effects In The High-Tech Market: The Case Of Research And Development Tools In Life Science Industry," International Journal of Innovation Management (ijim), World Scientific Publishing Co. Pte. Ltd., vol. 16(02), pages 1-28.
    18. Codrin-Marius Teiu, 2011. "The Impact Of The Financial Crisis On European E-Government Development," CES Working Papers, Centre for European Studies, Alexandru Ioan Cuza University, vol. 3(3), pages 429-439, September.
    19. Cui, Borui & Wang, Shengwei & Sun, Yongjun, 2014. "Life-cycle cost benefit analysis and optimal design of small scale active storage system for building demand limiting," Energy, Elsevier, vol. 73(C), pages 787-800.
    20. Mellon, Vicky & Bramwell, Bill, 2018. "The temporal evolution of tourism institutions," Annals of Tourism Research, Elsevier, vol. 69(C), pages 42-52.

    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:wsi:apjorx:v:30:y:2013:i:05:n:s0217595913500188. 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: Tai Tone Lim (email available below). General contact details of provider: http://www.worldscinet.com/apjor/apjor.shtml .

    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.