Powers of geometric intersection graphs and dispersion algorithms

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

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

Publication date: 4 December 2003

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

zbMATH Keywords

DispersionInterval graphsIntersection graphsCircular-arc graphsPowers of graphsTrapezoid graphs

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (7)

Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity ⋮ Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs ⋮ Unnamed Item ⋮ Distance-\(d\) independent set problems for bipartite and chordal graphs ⋮ Approximation Algorithm for the Distance-3 Independent Set Problem on Cubic Graphs ⋮ Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs ⋮ Mim-width. III. Graph powers and generalized distance domination problems

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
• Maximum independent sets of circular-arc graphs: Simplified algorithm and proofs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Powers of geometric intersection graphs and dispersion algorithms