Paper Search Console

Home Search Page About Contact

Journal Title

Title of Journal: Algorithmica

Search In Journal Title:

Abbravation: Algorithmica

Search In Journal Abbravation:

Publisher

Springer-Verlag

Search In Publisher:

DOI

10.1016/0032-0633(68)90006-8

Search In DOI:

ISSN

1432-0541

Search In ISSN:
Search In Title Of Papers:

Constructing Labeling Schemes through Universal Ma

Authors: Amos Korman David Peleg Yoav Rodeh
Publish Date: 2008/09/13
Volume: 57, Issue: 4, Pages: 641-652
PDF Link

Abstract

Let f be a function on pairs of vertices An f labeling scheme for a family of graphs ℱ labels the vertices of all graphs in ℱ such that for every graph G∈ℱ and every two vertices uv∈G fuv can be inferred by merely inspecting the labels of u and v The size of a labeling scheme is the maximum number of bits used in a label of any vertex in any graph in ℱ This paper illustrates that the notion of universal matrices can be used to efficiently construct flabeling schemesLet ℱn be a family of connected graphs of size at most n and let mathcalCmathcalFn denote the collection of graphs of size at most n such that each graph in mathcalCmathcalFn is composed of a disjoint union of some graphs in ℱn We first investigate methods for translating flabeling schemes for ℱn to flabeling schemes for mathcalCmathcalFn In particular we show that in many cases given an flabeling scheme of size gn for a graph family ℱn one can construct an flabeling scheme of size gn+log log n+O1 for mathcalCmathcalFn We also show that in several cases the above mentioned extra additive term of log log n+O1 is necessary In addition we show that the family of nnode graphs which are unions of disjoint circles enjoys an adjacency labeling scheme of size log n+O1 This illustrates a nontrivial example showing that the above mentioned extra additive term is sometimes not necessary We then turn to investigate distance labeling schemes on the class of circles of at most n vertices and show an upper bound of 15log n+O1 and a lower bound of 4/3log n−O1 for the size of any such labeling scheme


Keywords:

References


.
Search In Abstract Of Papers:
Other Papers In This Journal:

  1. On Minimum Sum of Radii and Diameters Clustering
  2. Integer Representation and Counting in the Bit Probe Model
  3. An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization
  4. New Approximation Algorithms for Minimum Cycle Bases of Graphs
  5. The (Weighted) Metric Dimension of Graphs: Hard and Easy Cases
  6. Aligning Two Convex Figures to Minimize Area or Perimeter
  7. Introduction for S.I. AofA14
  8. Balanced Scheduling toward Loss-Free Packet Queuing and Delay Fairness
  9. Detecting Regular Visit Patterns
  10. Linear Rank-Width of Distance-Hereditary Graphs I. A Polynomial-Time Algorithm
  11. Random Matrices and Codes for the Erasure Channel
  12. On Succinct Greedy Drawings of Plane Triangulations and 3-Connected Plane Graphs
  13. The Compressed Annotation Matrix: An Efficient Data Structure for Computing Persistent Cohomology
  14. Optimal Parallel Quantum Query Algorithms
  15. Average Case Network Lifetime on an Interval with Adjustable Sensing Ranges
  16. Maximum Series-Parallel Subgraph
  17. A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties
  18. Reconstructing Phylogenetic Level-1 Networks from Nondense Binet and Trinet Sets
  19. The Parameterized Complexity of Local Search for TSP, More Refined
  20. Approximating Fixation Probabilities in the Generalized Moran Process
  21. Approximation Algorithms for Scheduling with Reservations
  22. Algorithms for the Homogeneous Set Sandwich Problem
  23. A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling
  24. Computing Minimum Cuts by Randomized Search Heuristics
  25. An Approximation Algorithm for the Minimum Co-Path Set Problem
  26. Scheduling with an Orthogonal Resource Constraint
  27. Approximate Boyer-Moore String Matching for Small Alphabets
  28. Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth
  29. Between Treewidth and Clique-Width
  30. What’s the Frequency, Kenneth?: Sublinear Fourier Sampling Off the Grid
  31. Multi-sided Boundary Labeling
  32. A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs

Search Result: