Succinct encodings for families of interval graphs

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

zbMATH Keywords

interval graphsproper interval graphsunit interval graphssuccinct encodingspace efficient data structures

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

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

• OEIS

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