Perfectness and imperfectness of unit disk graphs on triangular lattice points

DOI10.1016/j.disc.2008.06.029zbMath1191.05050OpenAlexW2070234653MaRDI QIDQ1043621

J. Blot

Publication date: 9 December 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2008.06.029

zbMATH Keywords

approximation algorithmstable setperfect graphmulticoloringunit disk graphlattice graph

Mathematics Subject Classification ID

Perfect graphs (05C17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Online channel allocation in FDMA networks with reuse constraints
• Efficient bounds for the stable set, vertex cover and set packing problems
• Unit disk graphs
• Colouring proximity graphs in the plane
• Geometric algorithms and combinatorial optimization.
• Unit disk graph recognition is NP-hard
• On coloring unit disk graphs
• Graph imperfection. I
• Graph imperfection. II
• Algorithmic graph theory and perfect graphs
• A decomposition theorem for partially ordered sets
• LINEAR TIME APPROXIMATION ALGORITHM FOR MULTICOLORING LATTICE GRAPHS WITH DIAGONALS
• Channel assignment and weighted coloring
• Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees
• Simple heuristics for unit disk graphs
• Graph-Theoretic Concepts in Computer Science
• Static frequency assignment in cellular networks