Succinct permutation graphs

DOI10.1007/S00453-022-01039-2MaRDI QIDQ2684486zbMATH OpenOpenAlexFDO

Authors Konstantinos Tsakalidis, Sebastian Wild, Victor Zamaraev

Publication date 16 February 2023

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2010.04108

zbMATH Keywords

bipartite permutations graphscircular permutation graphsdistance oraclesgraph compressiongraph encodingpermutation graphssuccinct data structures

Mathematics Subject Classification ID

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

Recommendations

• On the succinct representation of unlabeled permutations
• Distance Labeling for Permutation Graphs
• Succinct data structures for families of interval graphs
• Succinct encodings for families of interval graphs
• scientific article; zbMATH DE number 2038722

Cites work

• A linear time algorithm to recognize circular permutation graphs
• A unifying look at data structures
• An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
• An optimal algorithm to solve the all-pairs shortest paths problem on permutation graphs
• Bipartite permutation graphs
• Changing base without losing space
• Circular permutation graphs
• Fully dynamic algorithm for recognition and modular decomposition of permutation graphs
• scientific article; zbMATH DE number 3908482 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• Localized and compact data-structure for comparability graphs
• Modular decomposition and transitive orientation
• On succinct representations of binary trees
• On testing isomorphism of permutation graphs
• On the speed of algebraically defined graph classes
• Optimal Distance Labeling for Interval Graphs and Related Graph Families
• Partially Ordered Sets
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
• Random generation and enumeration of bipartite permutation graphs
• Space-efficient preprocessing schemes for range minimum queries on static arrays
• Succinct data structures for chordal graphs
• Succinct encodings for families of interval graphs
• Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets
• Succinct navigational oracles for families of intersection graphs on a circle
• Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
• Transitive Orientation of Graphs and Identification of Permutation Graphs

Cited in

(13)

• Succinct navigational oracles for families of intersection graphs on a circle
• Succinct data structures for families of interval graphs
• Permutations in Coinductive Graph Representation
• Functigraphs: An extension of permutation graphs
• Permutation-exchange graphs that emulate the binary cube
• On the succinct representation of unlabeled permutations
• Permuting Web Graphs
• scientific article; zbMATH DE number 2038722 (Why is no real title available?)
• Succinct data structures for chordal graphs
• Succinct data structures for bounded clique-width graphs
• Succinct preferential-attachment graphs
• Succinct data structures for chordal graph with bounded leafage or vertex leafage
• Optimal distance labeling for permutation graphs

This page was built for publication: Succinct permutation graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2684486)