Sorry, you need to enable JavaScript to visit this website.

facebooktwittermailshare

Compact Representation of Graphs with Small Bandwidth and Treedepth

Abstract: 

We consider the problem of compact representation of graphs with small bandwidth as well as graphs with small treedepth. These parameters capture structural properties of graphs that come in useful in certain applications.
We present simple navigation oracles that support degree and adjacency queries in constant time and neighborhood query in constant time per neighbor. For graphs of bandwidth $k$, our oracle takes $(k+ \lceil \log 2k\rceil)n +o(kn$) bits. By way of an enumeration technique, we show that $(k-5\sqrt{k}-4)n-O(k^{2})$ bits are required to encode a graph of bandwidth $k$ and size $n$. For graphs of treedepth $k$, our oracle takes $(k+\lceil\log k \rceil +2)n + o(kn)$ bits. We present a lower bound that certifies our oracle is succinct for certain values of $k \in o(n)$.

up
0 users have voted:

Paper Details

Authors:
Submitted On:
22 April 2020 - 1:50pm
Short Link:
Type:
Tutorial
Event:
Presenter's Name:
Shahin Kamali
Paper Code:
204 (session 8)
Session:
Session 8
Document Year:
2020
Cite

Document Files

DCC-2020-Paper-204.pdf

(51)

Keywords

Additional Categories

Subscribe

[1] , "Compact Representation of Graphs with Small Bandwidth and Treedepth", IEEE SigPort, 2020. [Online]. Available: http://sigport.org/5089. Accessed: Aug. 12, 2020.
@article{5089-20,
url = {http://sigport.org/5089},
author = { },
publisher = {IEEE SigPort},
title = {Compact Representation of Graphs with Small Bandwidth and Treedepth},
year = {2020} }
TY - EJOUR
T1 - Compact Representation of Graphs with Small Bandwidth and Treedepth
AU -
PY - 2020
PB - IEEE SigPort
UR - http://sigport.org/5089
ER -
. (2020). Compact Representation of Graphs with Small Bandwidth and Treedepth. IEEE SigPort. http://sigport.org/5089
, 2020. Compact Representation of Graphs with Small Bandwidth and Treedepth. Available at: http://sigport.org/5089.
. (2020). "Compact Representation of Graphs with Small Bandwidth and Treedepth." Web.
1. . Compact Representation of Graphs with Small Bandwidth and Treedepth [Internet]. IEEE SigPort; 2020. Available from : http://sigport.org/5089