Vertex coloring edge-weighted digraphs

DOI10.1016/j.ipl.2015.05.007zbMath1330.05058OpenAlexW1929999343MaRDI QIDQ2348711

Magnús M. Halldórsson, Jörgen Bang-Jensen

Publication date: 15 June 2015

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2015.05.007

zbMATH Keywords

graph algorithmscoloringwireless schedulingedge-weighted digraphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (7)

Unnamed Item ⋮ Parameterized (Approximate) Defective Coloring ⋮ Limitations of current wireless link scheduling algorithms ⋮ Bounds and fixed-parameter algorithms for weighted improper coloring ⋮ Effective Wireless Scheduling via Hypergraph Sketches ⋮ Defective Coloring on Classes of Perfect Graphs ⋮ The Power of Oblivious Wireless Power

Cites Work

• Unnamed Item
• Unnamed Item
• Nearly optimal bounds for distributed wireless scheduling in the SINR model
• Improved algorithms for latency minimization in wireless networks
• Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Weighted improper colouring
• Directed weighted improper coloring for cellular channel allocation
• Splitting digraphs
• Distributed Contention Resolution in Wireless Networks
• Wireless Communication Is in APX
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Oblivious interference scheduling
• On Some Bounds on the Optimum Schedule Length in the SINR Model

This page was built for publication: Vertex coloring edge-weighted digraphs