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.1002/ceat.200700403

Search In DOI:

ISSN

1432-0541

Search In ISSN:
Search In Title Of Papers:

Detecting Regular Visit Patterns

Authors: Bojan Djordjevic Joachim Gudmundsson Anh Pham Thomas Wolle
Publish Date: 2009/11/21
Volume: 60, Issue: 4, Pages: 829-852
PDF Link

Abstract

We are given a trajectory mathcalT and an area mathcalA mathcalT might intersect mathcalA several times and our aim is to detect whether mathcalT visits mathcalA with some regularity eg what is the longest time span that a GPSGSM equipped elephant visited a specific lake on a daily weekly or yearly basis where the elephant has to visit the lake most of the days weeks or years but not necessarily on every day week or yearDuring the modelling of such applications we encountered an elementary problem on bitstrings that we call LDS LongestDenseSubstring The bits of the bitstring correspond to a sequence of regular time points in which a bit is set to 1 if and only if the trajectory mathcal T intersects the area mathcalA at the corresponding time point For the LDS problem we are given a string s as input and want to output a longest substring of s such that the ratio of 1’s in the substring is at least a certain thresholdIn our model LDS is a core problem for many applications that aim at detecting regularity of mathcalT intersecting  mathcalA We propose an optimal algorithm to solve LDS and also for related problems that are closer to applications we provide efficient algorithms for detecting regularity

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. Linear Rank-Width of Distance-Hereditary Graphs I. A Polynomial-Time Algorithm
  10. Random Matrices and Codes for the Erasure Channel
  11. On Succinct Greedy Drawings of Plane Triangulations and 3-Connected Plane Graphs
  12. The Compressed Annotation Matrix: An Efficient Data Structure for Computing Persistent Cohomology
  13. Optimal Parallel Quantum Query Algorithms
  14. Average Case Network Lifetime on an Interval with Adjustable Sensing Ranges
  15. Maximum Series-Parallel Subgraph
  16. A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties
  17. Reconstructing Phylogenetic Level-1 Networks from Nondense Binet and Trinet Sets
  18. The Parameterized Complexity of Local Search for TSP, More Refined
  19. Approximating Fixation Probabilities in the Generalized Moran Process
  20. Approximation Algorithms for Scheduling with Reservations
  21. Algorithms for the Homogeneous Set Sandwich Problem
  22. A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling
  23. Computing Minimum Cuts by Randomized Search Heuristics
  24. Constructing Labeling Schemes through Universal Matrices
  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: