Localized and compact data-structure for comparability graphs
DOI10.1016/J.DISC.2007.12.091zbMATH Open1221.05105OpenAlexW1985636891MaRDI QIDQ1025540FDOQ1025540
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
Recommendations
algorithmsdistributed algorithmspartially ordered setpermutation graphsdata-structuredistance labeling schemedistance queries
Partial orders, general (06A06) Data structures (68P05) Distance in graphs (05C12) Distributed algorithms (68W15)
Cites Work
- Topics in Intersection Graph Theory
- Title not available (Why is that?)
- Graph Classes: A Survey
- Distance labeling in graphs
- Planar graphs and poset dimension
- Approximate distance oracles
- All-Pairs Almost Shortest Paths
- Simple linear time recognition of unit interval graphs
- The Complexity of the Partial Order Dimension Problem
- Asteroidal Triple-Free Graphs
- Partial orders of dimension 2
- Partially Ordered Sets
- Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs
- Interval representations of planar graphs
- Shortest paths in digraphs of small treewidth. I: Sequential algorithms
- Compact oracles for reachability and approximate distances in planar digraphs
- Implicat Representation of Graphs
- Faster shortest-path algorithms for planar graphs
- A linear-time algorithm for proper interval graph recognition
- Title not available (Why is that?)
- Title not available (Why is that?)
- An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications
- Solving the all-pair shortest path query problem on interval and circular-arc graphs
- Distance labeling scheme and split decomposition
- Proximity-preserving labeling schemes
- Bypassing the embedding
- The interval number of a planar graph: Three intervals suffice
- Title not available (Why is that?)
- Query efficient implementation of graphs of bounded clique-width
- Oracles for bounded-length shortest paths in planar graphs
- Title not available (Why is that?)
- Compact and localized distributed data structures
- Optimal distance labeling for interval and circular-arc graphs
- Distance labeling schemes for well-separated graph classes
- Distance and routing labeling schemes for non-positively curved plane graphs
Cited In (12)
- Title not available (Why is that?)
- 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)
