Powers of geometric intersection graphs and dispersion algorithms
From MaRDI portal
Publication:1414578
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)
Dispersion; Interval graphs; Intersection graphs; Circular-arc graphs; Powers of graphs; Trapezoid graphs
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.)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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