Optimal edge-coloring with edge rate constraints

DOI10.1002/NET.21505MaRDI QIDQ2811307zbMATH OpenOpenAlexFDO

Authors Dariusz Dereniowski, Bernard Ries, Yori Zwols, Wieslaw Kubiak

Publication date 10 June 2016

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.21505

zbMATH Keywords

scheduling algorithmswireless networksedge coloringthroughput maximizationfractional edge coloringreedy maximal schedulingnearly bipartite graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Recommendations

• Densities, matchings, and fractional edge-colorings
• Constrained matching problems in bipartite graphs
• Edge-Coloring Problems for Graphs.
• Edge-Chromatic Scheduling with Simultaneity Constraints
• Fast edge colorings with fixed number of colors to minimize imbalance

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 227551 (Why is no real title available?)
• Algorithmic graph theory and perfect graphs
• Fast integer programming in fixed dimension
• Link scheduling in polynomial time
• Maximum matching and a polyhedron with 0,1-vertices
• Odd Minimum Cut-Sets and b-Matchings
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• Open Shop Scheduling to Minimize Finish Time
• Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks
• Sufficient conditions for stability of longest-queue-first scheduling: second-order properties using fluid limits
• The NP-Completeness of Edge-Coloring
• The chromatic index of multigraphs of order at most 10
• The chromatic index of nearly bipartite multigraphs
• The ellipsoid method and its consequences in combinatorial optimization

Cited in

(3)

• Optimal edge coloring of large graphs
• Fast Edge Colorings with Fixed Number of Colors to Minimize Imbalance
• Fast edge colorings with fixed number of colors to minimize imbalance

This page was built for publication: Optimal edge-coloring with edge rate constraints

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