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. E Penelope Holland & Alex James & Wendy A Ruscoe & Roger P Pech & Andrea E Byrom, 2015. "Climate-Based Models for Pulsed Resources Improve Predictability of Consumer Population Dynamics: Outbreaks of House Mice in Forest Ecosystems," PLOS ONE, Public Library of Science, vol. 10(3), pages 1-16, March.
    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. 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.
    9. 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.
    10. King, Aaron A. & Nguyen, Dao & Ionides, Edward L., 2016. "Statistical Inference for Partially Observed Markov Processes via the R Package pomp," Journal of Statistical Software, Foundation for Open Access Statistics, vol. 69(i12).
    11. 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.
    12. Mehmet Balcilar & Zeynel Abidin Ozdemir & Muhammad Shahbaz & Serkan Gunes, 2017. "Does Inflation Cause Gold Prices? Evidence from G7 Countries," Working Papers 15-31, Eastern Mediterranean University, Department of Economics.
    13. Andrei Sebastian Badea, 2011. "Perspectives On Improving Cohesion Policy Spending," CES Working Papers, Centre for European Studies, Alexandru Ioan Cuza University, vol. 3(1), pages 6-12, March.
    14. Kay Giesecke & Baeho Kim, 2011. "Systemic Risk: What Defaults Are Telling Us," Management Science, INFORMS, vol. 57(8), pages 1387-1405, August.
    15. Ana-Maria Pascu & Andreea Vasiliu, 2011. "International Financial Reporting Standard For Small And Medium-Sized Entities- A New Challenge For The European Union," CES Working Papers, Centre for European Studies, Alexandru Ioan Cuza University, vol. 3(1), pages 121-134, March.
    16. Licht, Amir N. & Poliquin, Christopher & Siegel, Jordan I. & Li, Xi, 2018. "What makes the bonding stick? A natural experiment testing the legal bonding hypothesis," Journal of Financial Economics, Elsevier, vol. 129(2), pages 329-356.
    17. Hyun Hak Kim, 2013. "Forecasting Macroeconomic Variables Using Data Dimension Reduction Methods: The Case of Korea," Working Papers 2013-26, Economic Research Institute, Bank of Korea.
    18. 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.
    19. 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.
    20. Kleine, Jens & Wagner, Niklas & Weller, Tim, 2016. "Openness endangers your wealth: Noise trading and the big five," Finance Research Letters, Elsevier, vol. 16(C), pages 239-247.

    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.