Succinct encodings for families of interval graphs
From MaRDI portal
Publication:2661990
DOI10.1007/S00453-020-00710-WOpenAlexW3017965136MaRDI QIDQ2661990FDOQ2661990
Authors: Hüseyin Acan, Sankardeep Chakraborty, Seungbum Jo, Srinivasa Rao Satti
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
Recommendations
- Succinct data structures for families of interval graphs
- Succinct encoding of arbitrary graphs
- On interval representations of graphs
- Bounded-depth succinct encodings and the structure they imply on graphs
- Succinct Representations of Arbitrary Graphs
- Succinct representations of separable graphs
- A note on succinct representations of graphs
- On the succinct representation of graphs
- Succinct Encodings of Graph Isomorphism
- Efficient enumeration of non-isomorphic interval graphs
interval graphsproper interval graphsunit interval graphssuccinct encodingspace efficient data structures
Cites Work
- Title not available (Why is that?)
- Introduction to algorithms.
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Linear-time recognition of circular-arc graphs
- Algorithmic graph theory and perfect graphs
- Succinct representation of balanced parentheses and static trees
- Efficient algorithms for interval graphs and circular-arc graphs
- The Complexity of Coloring Circular Arcs and Chords
- Title not available (Why is that?)
- Title not available (Why is that?)
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- Space-efficient preprocessing schemes for range minimum queries on static arrays
- Succinct indexes for strings, binary relations and multilabeled trees
- Intersection graphs of halflines and halfplanes
- Succinct data structures for flexible text retrieval systems
- Wavelet trees for all
- Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
- Rank/select operations on large alphabets
- A unified approach to approximating resource allocation and scheduling
- On space efficient two dimensional range minimum data structures
- Stability in circular arc graphs
- Succinct encoding of arbitrary graphs
- Complexity and algorithms for reasoning about time
- Solving the all-pair shortest path query problem on interval and circular-arc graphs
- Title not available (Why is that?)
- Succinct representations of permutations and functions
- Integer priority queues with decrease key in constant time and the single source shortest paths problem
- Succinct representations of planar maps
- On the enumeration of interval graphs
- Compact navigation and distance oracles for graphs with small treewidth
- On the classes of interval graphs of limited nesting and count of lengths
- Counting Interval Graphs
- Interval graphs and related topics
- Title not available (Why is that?)
- A framework for in-place graph algorithms
- Succinct data structures for families of interval graphs
- Title not available (Why is that?)
- Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
- AnO(m+nlogn) Algorithm for the Maximum-Clique Problem in Circular-Arc Graphs
- Space efficient linear time algorithms for BFS, DFS and applications
- Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS
Cited In (12)
- Distance queries over dynamic interval graphs
- Succinct data structures for SP, block-cactus and \(3\)-leaf power graphs
- Efficient neighborhood encoding for interval graphs and permutation graphs and \(O(n)\) breadth-first search
- Succinct encoding of arbitrary graphs
- Shorter Labeling Schemes for Planar Graphs
- Succinct Representations of Arbitrary Graphs
- Compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number
- Succinct data structures for bounded clique-width graphs
- Compact representation of graphs with bounded bandwidth or treedepth
- Succinct permutation graphs
- Succinct data structures for families of interval graphs
- Succinct navigational oracles for families of intersection graphs on a circle
Uses Software
This page was built for publication: Succinct encodings for families of interval graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2661990)