Facets of the graph coloring polytope
2002, Annals of Operations Research 116, 79-90, 2002Citas: 67
Agregar PDF Importar citas Plots Conexiones
Autor(es)
Pablo Coll and Javier Marenco and Isabel Méndez Díaz and Paula Zabala
Abstract
In this paper we present a study of the polytope associated to a classic linear integer programming formulation of the graph coloring problem. We determine some families of facets. This is the initial step for the development of a branch-and-cut algorithm to solve large instances of the graph coloring problem.
Plot de citas
Citas de Scrapping
| # | Año | #Citas | Título | Autores | Journal | Editor |
|---|---|---|---|---|---|---|
| 1 | 2010 | 335 | A supernodal formulation of vertex colouring with applications in course timetabling | EK Burke, J Mareček, AJ Parkes, H Rudová | Annals of Operations …, 2010 | Springer |
| 2 | 2006 | 279 | A branch-and-cut algorithm for graph coloring | I Méndez-Díaz, P Zabala | Discrete Applied Mathematics, 2006 | Elsevier |
| 3 | 2013 | 105 | Minimizing warehouse space with a dedicated storage policy | A Fumi, L Scarabotti… | International Journal of …, 2013 | journals.sagepub.com |
| 4 | 2008 | 151 | Packing and partitioning orbitopes | V Kaibel, M Pfetsch | Mathematical Programming, 2008 | Springer |
| 5 | 2008 | 142 | On the asymmetric representatives formulation for the vertex coloring problem | M Campêlo, VA Campos, RC Corrêa | Discrete Applied Mathematics, 2008 | Elsevier |
| 6 | 2012 | 127 | Exact solution of graph coloring problems via constraint programming and column generation | S Gualandi, F Malucelli | INFORMS Journal on Computing, 2012 | pubsonline.informs.org |
| 7 | 2013 | 96 | Dual connectivity in LTE HetNets with split control-and user-plane | A Zakrzewska, D López-Pérez… | 2013 IEEE …, 2013 | ieeexplore.ieee.org |
| 8 | 2012 | 94 | A branch-and-cut procedure for the Udine course timetabling problem | EK Burke, J Mareček, AJ Parkes, H Rudová | Annals of Operations …, 2012 | Springer |
| 9 | 2009 | 73 | Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results | P Hansen, M Labbé, D Schindl | Discrete Optimization, 2009 | Elsevier |
| 10 | 2014 | 41 | Multiproduct slot allocation heuristic to minimize storage space | C Battista, A Fumi, L Laura… | International Journal of …, 2014 | emerald.com |
| 11 | 2008 | 39 | A one-to-one correspondence between colorings and stable sets | D Cornaz, V Jost | Operations Research Letters, 2008 | Elsevier |
| 12 | 2020 | 13 | Content placement in cache networks using graph coloring | M Javedankherad, Z Zeinalpour-Yazdi… | IEEE Systems …, 2020 | ieeexplore.ieee.org |
| 13 | 2016 | 19 | Advances in combinatorial optimization: linear programming formulations of the traveling salesman and other hard combinatorial optimization problems | M Diaby, MH Karwan | 2016 | books.google.com |
| 14 | 2011 | 23 | Describing orbitopes by linear inequalities and projection based tools | A Loos | 2011 | core.ac.uk |
| 15 | 2010 | 30 | Linear programming formulation of the vertex colouring problem | M Diaby | … Journal of Mathematics in Operational Research, 2010 | inderscienceonline.com |
| 16 | 2019 | 12 | An integer programming approach to b-coloring | I Koch, J Marenco | Discrete Optimization, 2019 | Elsevier |
| 17 | 2013 | 16 | On the optimal design of a spectrum-switched optical network with multiple modulation formats and rates | I Popescu, I Cerutti, N Sambo… | Journal of Optical …, 2013 | opg.optica.org |
| 18 | 2011 | 15 | R Hansmann | 2011 | Cuvillier Verlag | |
| 19 | 2023 | 5 | Derivations of large classes of facet defining inequalities of the weak order polytope using ranking structures | AR Escobedo, R Yasmin | Journal of Combinatorial Optimization, 2023 | Springer |
| 20 | 2020 | 7 | Symmetry-breaking inequalities for ILP with structured sub-symmetry | P Bendotti, P Fouilhoux, C Rottner | Mathematical Programming, 2020 | Springer |
| 21 | 2023 | 1 | Polyhedral Approach to Total Matching and Total Coloring Problems | L Ferrarini | 2023 | boa.unimib.it |
| 22 | 2012 | 14 | Graph coloring facets from all-different systems | D Bergman, JN Hooker | … Conference on Integration of Artificial Intelligence …, 2012 | Springer |
| 23 | 2018 | 5 | Heuristic algorithms for graph coloring problems | W Sun | 2018 | theses.hal.science |
| 24 | 2010 | 12 | Facet-inducing web and antiweb inequalities for the graph coloring polytope | G Palubeckis | Discrete Applied Mathematics, 2010 | Elsevier |
| 25 | 2021 | 3 | Implementing cutting planes for the chromatic violation problem | D Delle Donne, MS Escalante… | Proceedings of the …, 2021 | openproceedings.org |
| 26 | 2014 | 9 | Graph coloring inequalities from all-different systems | D Bergman, JN Hooker | Constraints, 2014 | Springer |
| 27 | 2005 | 16 | Set covering and packing formulations of graph coloring: algorithms and first polyhedral results | P Hansen, M Labbé, D Schindl | 2005 | Citeseer |
| 28 | 2013 | 9 | New techniques for discrete optimization | D Bergman | 2013 | search.proquest.com |
| 29 | 2016 | 8 | Polyhedral studies of vertex coloring problems: The standard formulation | D Delle Donne, J Marenco | Discrete Optimization, 2016 | Elsevier |
| 30 | 2015 | 6 | Branch-and-cut algorithms for graph problems | B Yüceoglu | 2015 | cris.maastrichtuniversity.nl |
| 31 | 2020 | 4 | An exact algorithm for the edge coloring by total labeling problem | F Borghini, I Méndez-Díaz, P Zabala | Annals of Operations Research, 2020 | Springer |
| 32 | 2015 | 5 | Polyhedral studies of vertex coloring problems: The asymmetric representatives formulation | V Campos, RC Corrêa, DD Donne, J Marenco… | arXiv preprint arXiv …, 2015 | arxiv.org |
| 33 | 2022 | 1 | Handling sub-symmetries in integer linear programming using activation handlers | S Wessel, T Verhoeff, CAJ Hurkens | Master's thesis, Eindhoven …, 2022 | assets.w3.tue.nl |
| 34 | 2007 | 9 | An integer programming approach to equitable coloring problems | L Bahiense, S Jurkiewicz, A Lozano… | Proceedings of the …, 2007 | ws2.din.uem.br |
| 35 | 2007 | 5 | Polyhedral studies for minimum‐span graph labelling with integer distance constraints | V Mak | International Transactions in Operational Research, 2007 | Wiley Online Library |
| 36 | 2017 | 3 | The maximum‐impact coloring polytope | M Braga, D Delle Donne, R Linfati… | International …, 2017 | Wiley Online Library |
| 37 | 2004 | 7 | Some combinatorial optimization problems in graphs with applications in telecommunications and tomography | D Schindl | 2004 | infoscience.epfl.ch |
| 38 | 2023 | 0 | J Staszek | 2023 | Dissertation, Erlangen, Friedrich … | |
| 39 | 2018 | 2 | Cache placement phase based on graph coloring | M Javedankherad, Z Zeinalpour-Yazdi… | 2018 9th International …, 2018 | ieeexplore.ieee.org |
| 40 | 2016 | 6 | Estudios poliedrales de problemas de coloreo de grafos | DA Delle Donne | 2016 | bibliotecadigital.exactas.uba.ar |
| 41 | 2019 | 2 | Sub-symmetry-breaking inequalities for ILP with structured symmetry | P Bendotti, P Fouilhoux, C Rottner | … Conference, IPCO 2019, Ann Arbor, MI …, 2019 | Springer |
| 42 | 2022 | 0 | Minimum Conflict Balanced Graph Coloring Problem | NE Hanoğlu | 2022 | search.proquest.com |
| 43 | 2015 | 2 | Evaluation of transparent optical multiplexing techniques in transport networks | I Popescu | 2015 | hal.science |
| 44 | 2014 | 2 | Mixed Integer Linear Programming Models for Combinatorial Optimization Problems | F Della Croce | Concepts of Combinatorial Optimization, 2014 | Wiley Online Library |
| 45 | 2007 | 6 | Optimised grid-partitioning for block structured grids in parallel computing | D Junglas | 2007 | tuprints.ulb.tu-darmstadt.de |
| 46 | 2017 | 1 | Bilevel Clique Interdiction and Related Problems | T Becker | 2017 | repository.rice.edu |
| 47 | 2006 | 2 | On forests, stable sets and polyhedra associated with clique partitions | D Cornaz | Manuscript available on Optimization Online, 2006 | optimization-online.org |
| 48 | 2016 | 1 | A polyhedral investigation of star colorings | C Hojny, ME Pfetsch | Discrete Applied Mathematics, 2016 | Elsevier |
| 49 | 2013 | 1 | 4G and Beyond-Exploiting Heterogeneity in Mobile Networks | A Zakrzewska | 2013 | orbit.dtu.dk |
| 50 | 2013 | 1 | Branch and price for a reliability oriented darp model | A Quilliot, S Deleplanque, B Benoit | 2013 | hal.science |
| 51 | 2007 | 1 | A supernodal formulation of vertex colouring with applications in course timetabling | EK Burke, J Marecek, AJ Parkes… | Ann. Oper. Res, to appear …, 2007 | academia.edu |
| 52 | 2012 | 2 | Finite-domain cuts for graph coloring | D Bergman, JN Hooker | 2012 | Citeseer |
| 53 | 2017 | 0 | Exact algorithms for the Vertex Coloring Problem and its generalisations | IC Ternier | 2017 | theses.hal.science |
| 54 | 0 | Master Degree Thesis Report | I Popescu, I Cerutti, N Sambo | researchgate.net | ||
| 55 | 2015 | 0 | Decomposition of Integer Programs with Matchability Structure | F Dahms | 2015 | fdahms.com |
| 56 | 2007 | 2 | Modelagem matemática e aplicações do problema de coloração em grafos | D Lozano | 2007 | repositorio.unesp.br |
| 57 | 0 | 11vo Simposio Argentino de Investigacion Operativa, SIO 2013 | D Delle Donnea, J Marencob | academia.edu | ||
| 58 | 2009 | 0 | Quotient and power methods for the graph colouring problem | I Juhos | 2009 | doktori.bibl.u-szeged.hu |
| 59 | 0 | Graph Coloring via Constraint Programming-based Column Generation | SGF Malucelli | researchgate.net | ||
| 60 | 0 | Univerzitní rozvrhování pomocí celoˇcíselného programování | J Marecek | is.muni.cz | ||
| 61 | 2012 | 1 | Estudio poliedral y algoritmo branch-and-cut para el problema de coloreo equitativo en grafos | DE Severin | 2012 | bibliotecadigital.exactas.uba.ar |
| 62 | 2012 | 1 | 組合せ最適化問題に対する効率的な厳密解法のための問題の記述法に関する研究 | 乾伸雄 | (No Title), 2012 | ir.soken.ac.jp |
| 63 | 2008 | 1 | Limites inferiores para o problema de coloração de vértices via geração de cortes e colunas | CD Rodrigues | 2008 | repositorio.ufc.br |
| 64 | 2015 | 0 | MG Vilas Boas | 2015 | ||
| 65 | 2013 | 0 | Polyhedral studies on vertex coloring problems | D Delle Donne, J Marenco | XI Simposio Argentino de …, 2013 | sedici.unlp.edu.ar |
| 66 | 0 | 組み合わせ最適化問題に対する効率的な厳密解法のための問題の記述法に関する研究 | 乾伸雄， イヌイノブオ | ir.soken.ac.jp | ||
| 67 | 2013 | 0 | Mixed Integer Linear Programming Models for Combinatorial Optimization Problems | FD Croce | Concepts of Combinatorial Optimization, 2013 | Wiley Online Library |
| 68 | 0 | MRW CALVO, MI LJUBIC |