2-local 7/6-competitive algorithm for multicolouring a sub-class of hexagonal graphs

DOI10.1080/00207160802562531MaRDI QIDQ5747734zbMATH OpenOpenAlexFDO

Authors Janez Žerovnik, Petra Šparl

Publication date 14 September 2010

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/00207160802562531

zbMATH Keywords

2-local distributed algorithmapproximation algorithmcellular networksfrequency planninggraph colouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Approximation algorithms (68W25)

Recommendations

• 2-local 5/4-competitive algorithm for multicoloring triangle-free hexagonal graphs
• A distributed \(6/5\)-competitive algorithm for multicoloring triangle-free hexagonal graphs
• 2-local <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:mn>4</mml:mn><mml:mo stretchy="false">/</mml:mo><mml:mn>3</mml:mn></mml:math>-competitive algorithm for multicoloring hexagonal graphs
• A 1-Local 13/9-Competitive Algorithm for Multicoloring Hexagonal Graphs
• 1-local 7/5-competitive algorithm for multicoloring hexagonal graphs

Cites work

• 2-local <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:mn>4</mml:mn><mml:mo stretchy="false">/</mml:mo><mml:mn>3</mml:mn></mml:math>-competitive algorithm for multicoloring hexagonal graphs
• 2-local 5/4-competitive algorithm for multicoloring triangle-free hexagonal graphs
• A technique for multicoloring triangle-free hexagonal graphs
• Channel assignment and multicolouring of the induced subgraphs of the triangular lattice
• Channel assignment and weighted coloring
• Corrigendum: Static frequency assignment in cellular networks
• Distributed Online Frequency Assignment in Cellular Networks
• Finding a five bicolouring of a triangle-free subgraph of the triangular lattice
• Static frequency assignment in cellular networks

Cited in

(10)

• Finding a five bicolouring of a triangle-free subgraph of the triangular lattice
• 2-local 5/4-competitive algorithm for multicoloring triangle-free hexagonal graphs
• 1-local 7/5-competitive algorithm for multicoloring hexagonal graphs
• 1-Local 33/24-Competitive Algorithm for Multicoloring Hexagonal Graphs
• A 1-Local 13/9-Competitive Algorithm for Multicoloring Hexagonal Graphs
• A linear time algorithm for \(7\)-\([3]\)coloring triangle-free hexagonal graphs
• 2-local <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:mn>4</mml:mn><mml:mo stretchy="false">/</mml:mo><mml:mn>3</mml:mn></mml:math>-competitive algorithm for multicoloring hexagonal graphs
• A 1-local 4/3-competitive algorithm for multicoloring a subclass of hexagonal graphs
• A distributed \(6/5\)-competitive algorithm for multicoloring triangle-free hexagonal graphs
• Simpler multicoloring of triangle-free hexagonal graphs

This page was built for publication: 2-local 7/6-competitive algorithm for multicolouring a sub-class of hexagonal graphs

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