Succinct encodings for families of interval graphs
From MaRDI portal
Publication:2661990
DOI10.1007/s00453-020-00710-wOpenAlexW3017965136MaRDI QIDQ2661990
Seungbum Jo, Srinivasa Rao Satti, Hüseyin Acan, Sankardeep Chakraborty
Publication date: 8 April 2021
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-020-00710-w
interval graphsproper interval graphsunit interval graphssuccinct encodingspace efficient data structures
Related Items (4)
Compact representation of graphs with bounded bandwidth or treedepth ⋮ Compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number ⋮ Succinct permutation graphs ⋮ Shorter Labeling Schemes for Planar Graphs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Succinct encoding of arbitrary graphs
- Succinct representations of permutations and functions
- Compact navigation and distance oracles for graphs with small treewidth
- On space efficient two dimensional range minimum data structures
- Succinct data structures for flexible text retrieval systems
- Succinct representations of planar maps
- Interval graphs and related topics
- Intersection graphs of halflines and halfplanes
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Linear-time recognition of circular-arc graphs
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- Algorithmic graph theory and perfect graphs
- Succinct data structures for families of interval graphs
- Space efficient linear time algorithms for BFS, DFS and applications
- Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
- Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS
- Wavelet trees for all
- Succinct Representation of Balanced Parentheses and Static Trees
- On the enumeration of interval graphs
- Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
- Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
- Succinct indexes for strings, binary relations and multilabeled trees
- Rank/select operations on large alphabets
- Counting Interval Graphs
- Stability in circular arc graphs
- Efficient algorithms for interval graphs and circular-arc graphs
- The Complexity of Coloring Circular Arcs and Chords
- Complexity and algorithms for reasoning about time
- AnO(m+nlogn) Algorithm for the Maximum-Clique Problem in Circular-Arc Graphs
- Solving the all-pair shortest path query problem on interval and circular-arc graphs
- On the Classes of Interval Graphs of Limited Nesting and Count of Lengths
- A Framework for In-place Graph Algorithms
- A unified approach to approximating resource allocation and scheduling
- Integer priority queues with decrease key in constant time and the single source shortest paths problem
This page was built for publication: Succinct encodings for families of interval graphs