Interval routing schemes for circular-arc graphs

DOI10.1142/S0129054117500046zbMATH Open1360.68646arXiv1202.4160OpenAlexW2963191535MaRDI QIDQ2979675FDOQ2979675

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)

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.

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

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

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)

Cites Work

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

Cited In (2)

• Title not available (Why is that?)
• 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)