Interval routing schemes for circular-arc graphs

DOI10.1142/S0129054117500046MaRDI QIDQ2979675zbMATH OpenOpenAlexFDO

Authors Frank Gurski, Patrick Gwydion Poullie

Publication date 26 April 2017

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1202.4160

zbMATH Keywords

circular-arc graphscyclic permutationscompact routinginterval routing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62) Network design and communication in computer systems (68M10)

Abstract: Interval routing is a space efficient method to realize a distributed routing function. In this paper we show that every circular-arc graph allows a shortest path strict 2-interval routing scheme, i.e., by introducing a global order on the vertices and assigning at most two (strict) intervals in this order to the ends of every edge allows to depict a routing function that implies exclusively shortest paths. Since circular-arc graphs do not allow shortest path 1-interval routing schemes in general, the result implies that the class of circular-arc graphs has strict compactness 2, which was a hitherto open question. Additionally, we show that the constructed 2-interval routing scheme is a 1-interval routing scheme with at most one additional interval assigned at each vertex and we an outline algorithm to calculate the routing scheme for circular-arc graphs in O(n^2) time, where n is the number of vertices.

Recommendations

• Partial characterizations of networks supporting shortest path interval labeling schemes
• The compactness of interval routing for almost all graphs
• Interval routing schemes
• A survey on interval routing
• Interval routing schemes

Cites work

• $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
• A survey on interval routing
• A trade-off between space and efficiency for routing tables
• An Efficient Test for Circular-Arc Graphs
• AnO(m+nlogn) Algorithm for the Maximum-Clique Problem in Circular-Arc Graphs
• Characterizations and recognition of circular-arc graphs and subclasses: a survey
• Collective tree spanners of graphs
• Coloring a Family of Circular Arcs
• Designing networks with compact routing tables
• Interval Routing
• Interval routing schemes
• Labelling and Implicit Routing in Networks
• Linear-time recognition of circular-arc graphs
• Optimal Distance Labeling for Interval Graphs and Related Graph Families
• The complexity of the characterization of networks supporting shortest-path interval routing.
• Worst Case Bounds for Shortest Path Interval Routing

Cited in

(2)

• scientific article; zbMATH DE number 1424540 (Why is no real title available?)
• Partial characterizations of networks supporting shortest path interval labeling schemes

This page was built for publication: Interval routing schemes for circular-arc graphs

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