Implicat Representation of Graphs
From MaRDI portal
Publication:4030198
DOI10.1137/0405049zbMath0768.05082OpenAlexW2060963839WikidataQ56504575 ScholiaQ56504575MaRDI QIDQ4030198
Sampath Kannan, Steven Rudich, Moni Naor
Publication date: 1 April 1993
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0405049
Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Data structures (68P05)
Related Items (84)
An efficient implicit data structure for relation testing and searching in partially ordered sets ⋮ Better distance labeling for unweighted planar graphs ⋮ Average case analysis for tree labelling schemes ⋮ A Simple and Optimal Ancestry Labeling Scheme for Trees ⋮ Twin-width II: small classes ⋮ The space complexity of sum labelling ⋮ Proof labeling schemes ⋮ Induced-universal graphs for graphs with bounded maximum degree ⋮ GLOUDS: representing tree-like graphs ⋮ On the OBDD representation of some graph classes ⋮ On Universal Graphs of Minor Closed Families ⋮ How to Share a Secret, Infinitely ⋮ Parameterized complexity of the list coloring reconfiguration problem with graph parameters ⋮ Adjacency Labeling Schemes and Induced-Universal Graphs ⋮ Compact separator decompositions in dynamic trees and applications to labeling schemes ⋮ Graph parameters, implicit representations and factorial properties ⋮ An adjacency labeling scheme based on a decomposition of trees into caterpillars ⋮ A fast algorithm for the product structure of planar graphs ⋮ On the succinct representation of equivalence classes ⋮ Dot product representations of graphs ⋮ Orienting Dynamic Graphs, with Applications to Maximal Matchings and Adjacency Queries ⋮ Succinct encoding of arbitrary graphs ⋮ Near-optimal induced universal graphs for cycles and paths ⋮ Simple planar graph partition into three forests ⋮ Sparse universal graphs for planarity ⋮ Sphere and dot product representations of graphs ⋮ Optimal embeddings of the exchanged hypercube and the dual-cube as vertex-induced subgraphs of the hypercube ⋮ Graph product structure for non-minor-closed classes ⋮ Logical labeling schemes ⋮ Implicit representation of relations ⋮ Deterministic Fault-Tolerant Connectivity Labeling Scheme ⋮ Unnamed Item ⋮ On symbolic OBDD-based algorithms for the minimum spanning tree problem ⋮ General compact labeling schemes for dynamic trees ⋮ Distributed verification of minimum spanning trees ⋮ Distance labeling scheme and split decomposition ⋮ Optimal induced universal graphs for bounded-degree graphs ⋮ Unnamed Item ⋮ Constrained-path labellings on graphs of bounded clique-width ⋮ Succinct Representations of Arbitrary Graphs ⋮ Compact navigation and distance oracles for graphs with small treewidth ⋮ Implicit representations and factorial properties of graphs ⋮ Compact and localized distributed data structures ⋮ Distance and routing labeling schemes for cube-free median graphs ⋮ Induced Universal Hypergraphs ⋮ Implicit representation conjecture for semi-algebraic graphs ⋮ Better distance labeling for unweighted planar graphs ⋮ Labeling schemes for weighted dynamic trees ⋮ Secure Authenticated Comparisons ⋮ A simple greedy algorithm for dynamic graph orientation ⋮ Asymptotically optimal induced universal graphs ⋮ Representing graphs implicitly using almost optimal space ⋮ Randomized proof-labeling schemes ⋮ Shortest-path queries in static networks ⋮ An implicit representation of chordal comparability graphs in linear time ⋮ Constructing labeling schemes through universal matrices ⋮ On induced-universal graphs for the class of bounded-degree graphs ⋮ The space complexity of sum labelling ⋮ Graph parameters, implicit representations and factorial properties ⋮ Unnamed Item ⋮ On forbidden induced subgraphs for unit disk graphs ⋮ Combinatorics and algorithms for quasi-chain graphs ⋮ Fault-tolerant distance labeling for planar graphs ⋮ A note on models for graph representations ⋮ On the OBDD size for graphs of bounded tree- and clique-width ⋮ Combinatorics and algorithms for quasi-chain graphs ⋮ Labeling schemes for tree representation ⋮ Notes on graph product structure theory ⋮ Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games ⋮ Localized and compact data-structure for comparability graphs ⋮ Short Labels by Traversal and Jumping ⋮ A note on labeling schemes for graph connectivity ⋮ Unnamed Item ⋮ Isometric Universal Graphs ⋮ Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters ⋮ A counter-example to the probabilistic universal graph conjecture via randomized communication complexity ⋮ A dynamic distributed approach to representing proper interval graphs ⋮ Informative labeling schemes for graphs ⋮ Shorter Labeling Schemes for Planar Graphs ⋮ Efficient Local Representations of Graphs ⋮ Local representations using very short labels ⋮ Fault-tolerant distance labeling for planar graphs ⋮ Distance Labeling for Permutation Graphs ⋮ UNIVERSAL GRAPHS AND UNIVERSAL PERMUTATIONS
This page was built for publication: Implicat Representation of Graphs
