Succinct permutation graphs

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

zbMATH Keywords

permutation graphssuccinct data structuresgraph encodingdistance oraclesgraph compressionbipartite permutations graphscircular permutation graphs

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items (1)

Succinct data structures for bounded clique-width graphs

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