Interval Routing Schemes for Circular-Arc Graphs

DOI10.1142/S0129054117500046zbMath1360.68646arXiv1202.4160OpenAlexW2963191535MaRDI QIDQ2979675

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

compact routingcircular-arc graphscyclic permutationsinterval routing

Mathematics Subject Classification ID

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

Cites Work

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

This page was built for publication: Interval Routing Schemes for Circular-Arc Graphs