Succinct permutation graphs
From MaRDI portal
Publication:2684486
DOI10.1007/s00453-022-01039-2OpenAlexW3092624644MaRDI QIDQ2684486
Konstantinos Tsakalidis, Sebastian Wild, Victor Zamaraev
Publication date: 16 February 2023
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2010.04108
permutation graphssuccinct data structuresgraph encodingdistance oraclesgraph compressionbipartite permutations graphscircular permutation graphs
Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Random generation and enumeration of bipartite permutation graphs
- Localized and compact data-structure for comparability graphs
- Bipartite permutation graphs
- Modular decomposition and transitive orientation
- An optimal algorithm to solve the all-pairs shortest paths problem on permutation graphs
- An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
- Succinct navigational oracles for families of intersection graphs on a circle
- On the speed of algebraically defined graph classes
- On succinct representations of binary trees
- Succinct encodings for families of interval graphs
- Changing base without losing space
- Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
- Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
- Optimal Distance Labeling for Interval Graphs and Related Graph Families
- A unifying look at data structures
- On testing isomorphism of permutation graphs
- Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
- Circular permutation graphs
- A linear time algorithm to recognize circular permutation graphs
- Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets
- Transitive Orientation of Graphs and Identification of Permutation Graphs
- Partially Ordered Sets
- Fully dynamic algorithm for recognition and modular decomposition of permutation graphs
This page was built for publication: Succinct permutation graphs
