Compact representations of separable graphs
作者： Guy E. Blelloch , Ian A. Kash , Daniel K. Blandford
关键词: Clique-sum 、 Combinatorics 、 Discrete mathematics 、 Graph product 、 Mathematics 、 Indifference graph 、 Maximal independent set 、 Trapezoid graph 、 Modular decomposition 、 Pathwidth 、 Chordal graph
摘要: We consider the problem of representing graphs compactly while supporting queries efficiently. In particular we describe a data structure for n-vertex unlabeled that satisfy an O(nc)-separator theorem, c
acm.org
sci-hub.st 参考文章(25)
T. Suel, Jun Yuan, Compressing the graph structure of the Web data compression conference. pp. 213- 222 ,(2001) , 10.1109/DCC.2001.917152
Andrei Broder, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Sridhar Rajagopalan, Raymie Stata, Andrew Tomkins, Janet Wiener, Graph structure in the Web the web conference. ,vol. 33, pp. 309- 320 ,(2000) , 10.1016/S1389-1286(00)00083-9
Ian H. Witten, Managing gigabytes ,(1994)
Richie Chih-Nan Chuang, Ashim Garg, Xin He, Ming-Yang Kao, Hsueh-I Lu, Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses international colloquium on automata languages and programming. pp. 118- 129 ,(1998) , 10.1007/BFB0055046
D. Blandford, G. Blelloch, Index compression through document reordering data compression conference. pp. 342- 351 ,(2002) , 10.1109/DCC.2002.999972
György Turán, On the succinct representation of graphs Discrete Applied Mathematics. ,vol. 8, pp. 289- 294 ,(1984) , 10.1016/0166-218X(84)90126-4
Hsueh-I Lu, Linear-time compression of bounded-genus graphs into information-theoretically optimal number of bits symposium on discrete algorithms. pp. 223- 224 ,(2002) , 10.5555/545381.545409
Hana Galperin, Avi Wigderson, Succinct representations of graphs Information & Computation. ,vol. 56, pp. 183- 198 ,(1984) , 10.1016/S0019-9958(83)80004-7
Xin He, Ming-Yang Kao, Hsueh-I Lu, Linear-Time Succinct Encodings of Planar Graphs via Canonical Orderings SIAM Journal on Discrete Mathematics. ,vol. 12, pp. 317- 325 ,(1999) , 10.1137/S0895480197325031
Yi-Ting Chiang, Ching-Chi Lin, Hsueh-I Lu, Orderly spanning trees with applications to graph encoding and graph drawing symposium on discrete algorithms. pp. 506- 515 ,(2001) , 10.5555/365411.365518