skip to main content
10.1145/1146381.1146411acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
Article

Object location using path separators

Published: 23 July 2006 Publication History

Abstract

We study a novel separator property called k-path separable. Roughly speaking, a k-path separable graph can be recursively separated into smaller components by sequentially removing k shortest paths. Our main result is that every minor free weighted graph is k-path separable. We then show that k-path separable graphs can be used to solve several object location problems: (1) a small-worldization with an average poly-logarithmic number of hops; (2) an (1 + ε)-approximate distance labeling scheme with O(log n) space labels; (3) a stretch-(1 + ε) compact routing scheme with tables of poly-logarithmic space; (4) an (1 + ε)-approximate distance oracle with O(n log n) space and O(log n) query time. Our results generalizes to much wider classes of weighted graphs, namely to bounded-dimension isometric sparable graphs.

References

[1]
I. Abraham and C. Gavoille, Object location using path separators, Research Report RR-1394-06, LaBRI, University of Bordeaux 1, France, Mar. 2006.]]
[2]
I. Abraham, C. Gavoille, A. V. Goldberg, and D. Malkhi, Routing in networks with low doubling dimension, in 26th International Conference on Distributed Computing Systems (ICDCS), IEEE Computer Society Press, July 2006. To appear.]]
[3]
I. Abraham, C. Gavoille, and D. Malkhi, Compact routing for graphs excluding a fixed minor, in 19th International Symposium on Distributed Computing (DISC), vol. 3724 of LNCS, Springer, Sept. 2005, pp. 442--456.]]
[4]
---, On space-stretch trade-offs: Lower bounds, in 18th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), ACM Press, July 2006.]]
[5]
J. Alber, H. Fernau, and R. Niedermeier, Graph separators: A parameterized view, Journal of Computer and System Sciences, 67 (2003), pp. 808--832.]]
[6]
N. Alon, P. D. Seymour, and R. Thomas, A separator theorem for graphs with an excluded minor and its applications, in 22nd Annual ACM Symposium on Theory of Computing (STOC), ACM Press, May 1990, pp. 293--299.]]
[7]
---, Planar separators, SIAM Journal on Discrete Mathematics, 7 (1994), pp. 184--193.]]
[8]
B. Awerbuch and D. Peleg, Sparse partitions, in 31st Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society Press, Oct. 1990, pp. 503--513.]]
[9]
---, Routing with polynomial communication-space trade-off, SIAM Journal on Discrete Mathematics, 5 (1992), pp. 151--162.]]
[10]
H. T.-H. Chan, A. Gupta, B. M. Maggs, and S. Zhou, On hierarchical routing in doubling metrics, in 16th Symposium on Discrete Algorithms (SODA), ACM-SIAM, Jan. 2005.]]
[11]
E. D. Demaine, F. V. Fomin, M. T. Hajiaghayi, and D. M. Thilikos, Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs, Journal of the ACM, 52 (2005), pp. 866--893.]]
[12]
E. D. Demaine and M. Hajiaghayi, Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality, in 15th Symposium on Discrete Algorithms (SODA), ACM-SIAM, Jan. 2005, pp. 682--689.]]
[13]
R. Diestel and R. Thomas, Excluding a countable clique, Journal of Combinatorial Theory, Series B, 76 (1999), pp. 41--67.]]
[14]
H. N. Djidjev and S. M. Venkatesan, Reduced constants for simple cycle graph separation, Acta Informatica, 34 (1997), pp. 231--243.]]
[15]
P. Duchon, N. Hanusse, E. Lebhar, and N. Schabanel, Could any graph be turned into a small-world?, Research Report 2004-62, LIP, école Normale Supérieure de Lyon, Dec. 2004.]]
[16]
---, Could any graph be turned into a small-world?, Theoretical Computer Science, 355 (2006), pp. 96--103.]]
[17]
U. Feige, M. Hajiaghayi, and J. R. Lee, Improved approximation algorithms for minimum-weight vertex separators, in 37th Annual ACM Symposium on Theory of Computing (STOC), ACM Press, May 2005.]]
[18]
P. Flocchini and F. L. Luccio, A new compact routing technique on series parallel networks, Theory of Computing Systems, 36 (2003), pp. 137--157.]]
[19]
P. Fraigniaud, A new perspective on the small-world phenomenon: Greedy routing in tree-decomposed graphs, in 13th Annual European Symposium on Algorithms (ESA), vol. 3669 of LNCS, Springer, Oct. 2005, pp. 791--802.]]
[20]
P. Fraigniaud and C. Gavoille, Routing in trees, in 28th International Colloquium on Automata, Languages and Programming (ICALP), vol. 2076 of LNCS, Springer, July 2001, pp. 757--772.]]
[21]
G. N. Frederickson and R. Janardan, Designing networks with compact routing tables, Algorithmica, 3 (1988), pp. 171--190.]]
[22]
---, Efficient message routing in planar networks, SIAM Journal on Computing, 18 (1989), pp. 843--857.]]
[23]
B. Fu, Theory and application of width bounded geometric separator, in 23rd Annual Symposium on Theoretical Aspects of Computer Science (STACS), vol. 3884 of LNCS, Springer, Feb. 2006, pp. 277--288.]]
[24]
C. Gavoille and M. Gengler, Space-efficiency of routing schemes of stretch factor three, Journal of Parallel and Distributed Computing, 61 (2001), pp. 679--687.]]
[25]
C. Gavoille, D. Peleg, S. Pérennès, and R. Raz, Distance labeling in graphs, Journal of Algorithms, 53 (2004), pp. 85--112.]]
[26]
J. R. Gilbert, J. P. Hutchinson, and R. E. Tarjan, A separation theorem for graphs of bounded genus, Journal of Algorithms, 5 (1984), pp. 391--407.]]
[27]
M. Grohe, Local tree-width, excluded minors, and approximation algorithms, Combinatorica, 23 (2003), pp. 613--632.]]
[28]
A. Gupta, A. Kumar, and R. Rastogi, Traveling with a pez dispenser (or, routing issues in MPLS), SIAM Journal on Computing, 34 (2005), pp. 453--474.]]
[29]
J. Kleinberg, The small-world phenomenon: An algorithmic perspective, in 32nd Annual ACM Symposium on Theory of Computing (STOC), ACM Press, May 2000, pp. 163--170.]]
[30]
---, Complex networks and decentralized search algorithms, in International Congress of Mathematicians (ICM), ACM Press, Aug. 2006. To appear.]]
[31]
T. Kloks, Treewidth: Computations and Approximations, vol. 842 of LNCS, Springer-Verlag, June 1994.]]
[32]
K. A. Laing, Brief announcement: Name-independent compact routing in trees, in 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC), ACM Press, July 2004, pp. 382--382.]]
[33]
R. J. Lipton and R. E. Tarjan, A separator theorem for planar graphs, SIAM Journal on Applied Mathematics, 36 (1979), pp. 177--189.]]
[34]
B. Mohar and C. Thomassen, Graphs on Surfaces, The Johns Hopkins university Press, 2001.]]
[35]
S. A. Plotkin, S. B. Rao, and W. D. Smith, Shallow excluded minors and improved graph decomposition, in 5th Symposium on Discrete Algorithms (SODA), ACM-SIAM, 1994, pp. 462--470.]]
[36]
B. Reed and D. R. Wood, A linear time algorithm to find a separation in a graph with an excluded minor, 2005. Full version of EuroComb '05.]]
[37]
N. Robertson and P. D. Seymour, Graph minors. V. Excluding a planar graph, Journal of Combinatorial Theory, Series B, 41 (1986), pp. 92--114.]]
[38]
---, Graph minors. XIII. The disjoint paths problem, Journal of Combinatorial Theory, Series B, 63 (1995), pp. 65--110.]]
[39]
---, Graph minors. XVI. Excluding a non-planar graph, Journal of Combinatorial Theory, Series B, 89 (2003), pp. 43--76.]]
[40]
N. Robertson, P. D. Seymour, and R. Thomas, Quickly excluding a planar graph, Journal of Combinatorial Theory, Series B, 62 (1994), pp. 323--348.]]
[41]
A. Slivkins, Distance estimation and object location via rings of neighbors, in 24th Annual ACM Symposium on Principles of Distributed Computing (PODC), ACM Press, July 2005, pp. 41--50. Appears earlier as Cornell CIS technical report TR2005-1977.]]
[42]
K. Talwar, Bypassing the embedding: Algorithms for low dimensional metrics, in 36th Annual ACM Symposium on Theory of Computing (STOC), ACM Press, June 2004, pp. 281--290.]]
[43]
A. Thomason, The extremal function for complete minors, Journal of Combinatorial Theory, Series B, 81 (2001), pp. 318--338.]]
[44]
M. Thorup, Compact oracles for reachability and approximate distances in planar digraphs, Journal of the ACM, 51 (2004), pp. 993--1024.]]
[45]
M. Thorup and U. Zwick, Approximate distance oracles, Journal of the ACM, 52 (2005), pp. 1--24.]]

Cited By

View all
  • (2024)Local certification of graph decompositions and applications to minor-free classesJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104954193:COnline publication date: 1-Nov-2024
  • (2023)Reliable Spanners for Metric SpacesACM Transactions on Algorithms10.1145/356335619:1(1-27)Online publication date: 9-Mar-2023
  • (2023)Labelings vs. Embeddings: On Distributed and Prioritized Representations of DistancesDiscrete & Computational Geometry10.1007/s00454-023-00565-2Online publication date: 15-Sep-2023
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing
July 2006
230 pages
ISBN:1595933840
DOI:10.1145/1146381
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. compact routing
  2. excluded minor
  3. separator

Qualifiers

  • Article

Conference

PODC06

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)19
  • Downloads (Last 6 weeks)1
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Local certification of graph decompositions and applications to minor-free classesJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104954193:COnline publication date: 1-Nov-2024
  • (2023)Reliable Spanners for Metric SpacesACM Transactions on Algorithms10.1145/356335619:1(1-27)Online publication date: 9-Mar-2023
  • (2023)Labelings vs. Embeddings: On Distributed and Prioritized Representations of DistancesDiscrete & Computational Geometry10.1007/s00454-023-00565-2Online publication date: 15-Sep-2023
  • (2022)Bypassing the surface embedding: approximation schemes for network design in minor-free graphsProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520049(343-356)Online publication date: 9-Jun-2022
  • (2022) Embeddings of Planar Quasimetrics into Directed ℓ 1 and Polylogarithmic Approximation for Directed Sparsest-Cut 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS52979.2021.00055(480-491)Online publication date: Feb-2022
  • (2022)Fault-tolerant distance labeling for planar graphsTheoretical Computer Science10.1016/j.tcs.2022.03.020918:C(48-59)Online publication date: 29-May-2022
  • (2022)Covering metric spaces by few treesJournal of Computer and System Sciences10.1016/j.jcss.2022.06.001130(26-42)Online publication date: Dec-2022
  • (2022)Greedy routing and the algorithmic small-world phenomenonJournal of Computer and System Sciences10.1016/j.jcss.2021.11.003125(59-105)Online publication date: May-2022
  • (2022)Decentralized Graph Processing for Reachability QueriesAdvanced Data Mining and Applications10.1007/978-3-031-22064-7_36(505-519)Online publication date: 24-Nov-2022
  • (2021)Coresets for clustering in excluded-minor graphs and beyondProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458223(2679-2696)Online publication date: 10-Jan-2021
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media