An exact algorithm for the edge coloring by total labeling problem

DOI10.1007/S10479-018-2977-XMaRDI QIDQ2178329zbMATH OpenOpenAlexWikidataFDO

Authors Fabrizio Borghini, Paula Zabala, Isabel Méndez-Díaz

Publication date 11 May 2020

Published in Annals of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10479-018-2977-x

zbMATH Keywords

branch-and-cutedge coloringgraph coloringtotal labeling

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Communication networks in operations research (90B18) Management decision making, including multiple objectives (90B50) Integer programming (90C10) Nonlinear programming (90C30) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• scientific article; zbMATH DE number 5178701
• A polyhedral approach to edge coloring
• Total coloring and total matching: polyhedra and facets
• Edge colouring by total labellings
• Edge coloring total \(k\)-labeling of generalized Petersen graphs

Cites work

• A branch-and-cut procedure for the Udine course timetabling problem
• A branch-and-price algorithm for the (k,c)-coloring problem
• A comparison of two edge-coloring formulations
• A constructive proof of Vizing's theorem
• A Cutting Plane Algorithm for the Linear Ordering Problem
• Edge coloring total \(k\)-labeling of generalized Petersen graphs
• Edge colouring by total labellings
• Facets of the graph coloring polytope
• Facets of the linear ordering polytope
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• Models and solution techniques for frequency assignment problems
• New methods to color the vertices of a graph
• On irregular total labellings
• Solving vertex coloring problems as maximum weight stable set problems

Cited in

(5)

• Contrast in greyscales of graphs
• Exact algorithms for a discrete metric labeling problem
• A backtracking algorithm for solving the nearly equitable strong edge-coloring problem on transportation network
• An exact algorithm for the adjacent vertex distinguishing sum edge coloring problem
• Edge colouring by total labellings

Describes a project that uses

Uses Software

• CPLEX
• CALMA

This page was built for publication: An exact algorithm for the edge coloring by total labeling problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2178329)