Localized and compact data-structure for comparability graphs

DOI10.1016/J.DISC.2007.12.091MaRDI QIDQ1025540zbMATH OpenOpenAlexFDO

Authors Fabrice Bazzaro, Cyril Gavoille

Publication date 19 June 2009

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2007.12.091

zbMATH Keywords

algorithmsdistributed algorithmspartially ordered setpermutation graphsdata-structuredistance labeling schemedistance queries

Mathematics Subject Classification ID

Partial orders, general (06A06) Data structures (68P05) Distance in graphs (05C12) Distributed algorithms (68W15)

Recommendations

• Algorithms and Computation
• Distance Labeling for Permutation Graphs
• Compact representation of posets
• Succinct posets
• Distance labeling in graphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 2079335 (Why is no real title available?)
• scientific article; zbMATH DE number 2079400 (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?)
• A linear-time algorithm for proper interval graph recognition
• All-Pairs Almost Shortest Paths
• An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications
• Approximate distance oracles
• Asteroidal Triple-Free Graphs
• Bypassing the embedding
• Compact and localized distributed data structures
• Compact oracles for reachability and approximate distances in planar digraphs
• Distance and routing labeling schemes for non-positively curved plane graphs
• Distance labeling in graphs
• Distance labeling scheme and split decomposition
• Distance labeling schemes for well-separated graph classes
• Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs
• Faster shortest-path algorithms for planar graphs
• Graph Classes: A Survey
• Implicat Representation of Graphs
• Interval representations of planar graphs
• Optimal distance labeling for interval and circular-arc graphs
• Oracles for bounded-length shortest paths in planar graphs
• Partial orders of dimension 2
• Partially Ordered Sets
• Planar graphs and poset dimension
• Proximity-preserving labeling schemes
• Query efficient implementation of graphs of bounded clique-width
• Shortest paths in digraphs of small treewidth. I: Sequential algorithms
• Simple linear time recognition of unit interval graphs
• Solving the all-pair shortest path query problem on interval and circular-arc graphs
• The Complexity of the Partial Order Dimension Problem
• The interval number of a planar graph: Three intervals suffice
• Topics in Intersection Graph Theory

Cited in

(12)

• scientific article; zbMATH DE number 7561659 (Why is no real title available?)
• Optimization of a data dependence graph for the local microcode compaction problem. II: Algorithms and experimental verification
• Dimension-2 poset competition numbers and dimension-2 poset double competition numbers
• Distance Labeling Schemes for $$K_4$$-Free Bridged Graphs
• Additive spanners and distance and routing labeling schemes for hyperbolic graphs
• Distance and routing labeling schemes for cube-free median graphs
• Algorithms and Computation
• Succinct permutation graphs
• Compact representation of posets
• Succinct navigational oracles for families of intersection graphs on a circle
• Improved enumeration of simple topological graphs
• Distance labeling schemes for \(K_4\)-free bridged graphs

This page was built for publication: Localized and compact data-structure for comparability graphs

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