Distance Labeling for Permutation Graphs

DOI10.1016/j.endm.2005.06.098zbMath1186.05111OpenAlexW1966909799MaRDI QIDQ3439382

Fabrice Bazzaro, Cyril Gavoille

Publication date: 29 May 2007

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2005.06.098

zbMATH Keywords

algorithmsdistributed algorithmspermutation graphsdata-structuredistance labeling schemedistance queries

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The interval number of a planar graph: Three intervals suffice
• Interval representations of planar graphs
• Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs
• Query efficient implementation of graphs of bounded clique-width
• Distance labeling scheme and split decomposition
• Shortest paths in digraphs of small treewidth. I: Sequential algorithms
• An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications
• Bypassing the embedding
• Implicat Representation of Graphs
• Topics in Intersection Graph Theory
• Solving the all-pair shortest path query problem on interval and circular-arc graphs
• Distance labeling in graphs
• All-Pairs Almost Shortest Paths
• Proximity-preserving labeling schemes
• Compact and localized distributed data structures
• Approximate distance oracles
• Partial orders of dimension 2
• Algorithms - ESA 2003
• Faster shortest-path algorithms for planar graphs

This page was built for publication: Distance Labeling for Permutation Graphs