Distance Labeling for Permutation Graphs

DOI10.1016/J.ENDM.2005.06.098MaRDI QIDQ3439382zbMATH OpenOpenAlexFDO

Authors 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

algorithmsdata-structuredistance labeling schemedistance queriesdistributed algorithmspermutation graphs

Mathematics Subject Classification ID

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

Recommendations

• Distance labellings of graphs
• Distance labeling in graphs
• Distance and connectivity measures in permutation graphs
• Permutation labeling of graphs
• Distance labeling in graphs (extended abstract)
• Distance-two labelings of graphs
• Labeling bipartite permutation graphs with a condition at distance two
• scientific article; zbMATH DE number 1409224
• Distance magic labelling of graphs
• Permutation labeling for some special graphs

Cites work

• All-Pairs Almost Shortest Paths
• An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications
• Approximate distance oracles
• Bypassing the embedding
• Compact and localized distributed data structures
• Distance labeling in graphs
• Distance labeling scheme and split decomposition
• Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs
• Faster shortest-path algorithms for planar graphs
• scientific article; zbMATH DE number 2079400 (Why is no real title available?)
• scientific article; zbMATH DE number 1500540 (Why is no real title available?)
• scientific article; zbMATH DE number 1875437 (Why is no real title available?)
• scientific article; zbMATH DE number 6472574 (Why is no real title available?)
• Implicat Representation of Graphs
• Interval representations of planar graphs
• Optimal distance labeling for interval and circular-arc graphs
• Partial orders of dimension 2
• Proximity-preserving labeling schemes
• Query efficient implementation of graphs of bounded clique-width
• Shortest paths in digraphs of small treewidth. I: Sequential algorithms
• Solving the all-pair shortest path query problem on interval and circular-arc graphs
• The interval number of a planar graph: Three intervals suffice
• Topics in Intersection Graph Theory

Cited in

(7)

• Localized and compact data-structure for comparability graphs
• Distance and connectivity measures in permutation graphs
• Succinct permutation graphs
• Using Graphs for the Analysis and Construction of Permutation Distance-Preserving Mappings
• Graph distance‐dependent labeling related to code assignment in computer networks
• Optimal distance labeling for permutation graphs
• \(O(1)\) query time algorithm for all pairs shortest distances on permutation graphs

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

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