Localized and compact data-structure for comparability graphs
From MaRDI portal
Publication:1025540
DOI10.1016/j.disc.2007.12.091zbMath1221.05105OpenAlexW1985636891MaRDI QIDQ1025540
Cyril Gavoille, Fabrice Bazzaro
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
algorithmspartially ordered setdistributed algorithmspermutation graphsdata-structuredistance labeling schemedistance queries
Partial orders, general (06A06) Distance in graphs (05C12) Data structures (68P05) Distributed algorithms (68W15)
Related Items (9)
Improved enumeration of simple topological graphs ⋮ Distance Labeling Schemes for $$K_4$$-Free Bridged Graphs ⋮ Succinct permutation graphs ⋮ Additive spanners and distance and routing labeling schemes for hyperbolic graphs ⋮ Distance and routing labeling schemes for cube-free median graphs ⋮ Dimension-2 poset competition numbers and dimension-2 poset double competition numbers ⋮ Unnamed Item ⋮ Succinct navigational oracles for families of intersection graphs on a circle ⋮ Distance labeling schemes for \(K_4\)-free bridged graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A linear-time algorithm for proper interval graph recognition
- Simple linear time recognition of unit interval graphs
- The interval number of a planar graph: Three intervals suffice
- Interval representations of planar graphs
- Planar graphs and poset dimension
- 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
- Distance labeling schemes for well-separated graph classes
- An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications
- Oracles for bounded-length shortest paths in planar graphs
- Distance and routing labeling schemes for non-positively curved plane graphs
- Approximate distance oracles
- Bypassing the embedding
- The Complexity of the Partial Order Dimension Problem
- Implicat Representation of Graphs
- Topics in Intersection Graph Theory
- Graph Classes: A Survey
- Asteroidal Triple-Free Graphs
- 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
- Compact oracles for reachability and approximate distances in planar digraphs
- Partial orders of dimension 2
- Partially Ordered Sets
- Algorithms - ESA 2003
- Faster shortest-path algorithms for planar graphs
This page was built for publication: Localized and compact data-structure for comparability graphs
