Powers of geometric intersection graphs and dispersion algorithms

DOI10.1016/S0166-218X(03)00386-XzbMath1029.05106MaRDI QIDQ1414578

Peter Damaschke, Magnús M. Halldórsson, Geir Agnarsson

Publication date: 4 December 2003

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

zbMATH Keywords

Dispersion; Interval graphs; Intersection graphs; Circular-arc graphs; Powers of graphs; Trapezoid graphs

Mathematics Subject Classification ID

05C12: Distance in graphs

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

05C62: Graph representations (geometric and intersection representations, etc.)

Related Items

Distance-\(d\) independent set problems for bipartite and chordal graphs, Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs, Approximation Algorithm for the Distance-3 Independent Set Problem on Cubic Graphs

Cites Work

• Trapezoid graphs and generalizations, geometry and algorithms
• Distances in cocomparability graphs and their powers
• Linear time algorithms on circular-arc graphs
• An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
• On computing the length of longest increasing subsequences
• On powers of \(m\)-trapezoid graphs
• On powers of circular arc graphs and proper circular arc graphs
• Facility dispersion problems under capacity and cost constraints
• Minimum Cuts for Circular-Arc Graphs
• The Complexity of the Partial Order Dimension Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item