Change search
Refine search result
1 - 26 of 26
Cite
Citation style
• apa
• ieee
• modern-language-association-8th-edition
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf
Rows per page
• 5
• 10
• 20
• 50
• 100
• 250
Sort
• Standard (Relevance)
• Author A-Ö
• Author Ö-A
• Title A-Ö
• Title Ö-A
• Publication type A-Ö
• Publication type Ö-A
• Issued (Oldest first)
• Created (Oldest first)
• Last updated (Oldest first)
• Disputation date (earliest first)
• Disputation date (latest first)
• Standard (Relevance)
• Author A-Ö
• Author Ö-A
• Title A-Ö
• Title Ö-A
• Publication type A-Ö
• Publication type Ö-A
• Issued (Oldest first)
• Created (Oldest first)
• Last updated (Oldest first)
• Disputation date (earliest first)
• Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
• 1.
Lunds universitet.
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science. IMFM, Ljubljana, Slovenia.
Comment on "self-indexed sort"1996In: SIGPLAN notices, ISSN 0362-1340, E-ISSN 1558-1160, Vol. 31, no 8, p. 40-41Article in journal (Other academic)
• 2.
University of Waterloo.
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
Architecture of KRPAN1996In: Elektrotehniski Vestnik, ISSN 0013-5852, Vol. 63, no 2, p. 65-68Article in journal (Refereed)

In the paper we address the operation of an agency that provides information in a newspaper-like form on the information highway. We describe the software architecture and the physical layout of KRPAN, a kernel that provides the support necessary to operate such an agency. KRPAN is a distributed system which employs intelligent caching to improve space and network utilization. The implementation of KRPAN relies on standardized formats of data which permits usage of commonly available tools. At the end we touch legal and ethical questions and describe how KRPAN helps to solve them.

• 3.
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Embedded Internet Systems Lab.
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science. Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science. Luleå tekniska universitet. Luleå University of Technology, Department of Engineering Sciences and Mathematics, Mathematical Science.
Minimum curvature variation B-splines: validation of a path-planning model2004Report (Other academic)
• 4.
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Embedded Internet Systems Lab.
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science. University of Primorska, Slovenia. . Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science. Luleå tekniska universitet. Luleå University of Technology, Department of Engineering Sciences and Mathematics, Mathematical Science.
Planning smooth and obstacle-avoiding b-spline paths for autonomous mining vehicles2010In: IEEE Transactions on Automation Science and Engineering, ISSN 1545-5955, E-ISSN 1558-3783, Vol. 7, no 1, p. 167-172Article in journal (Refereed)

We study the problem of automatic generation of smooth and obstacle-avoiding planar paths for efficient guidance of autonomous mining vehicles. Fast traversal of a path is of special interest. We consider four-wheel four-gear articulated vehicles and assume that we have an a priori knowledge of the mine wall environment in the form of polygonal chains. Computing quartic uniform B-spline curves, minimizing curvature variation, staying at least at a proposed safety margin distance from the mine walls, we plan high speed paths.

• 5.
Luleå tekniska universitet.
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
Formal verification of a trie-based data structure2005Conference paper (Refereed)
• 6.
School of Computer Science, Carleton University, Ottawa.
University of Karlskona/Ronneby. Massachusetts Institute of Technology, Laboratory for Computer Science, Cambridge. Department of Computer Science, Hong Kong University of Science and Technology. Department of Computer Science, University of Waterloo, Ontario. School of Computer Science, Carleton University, Ottawa. Department of Computer Science, University of Waterloo, Ontario.
Online routing in convex subdivisions2002In: International journal of computational geometry and applications, ISSN 0218-1959, Vol. 12, no 4, p. 283-295Article in journal (Refereed)

We consider online routing algorithms for finding paths between the vertices of plane graphs. We show (1) there exists a routing algorithm for arbitrary triangulations that has no memory and uses no randomization, (2) no equivalent result is possible for convex subdivisions, (3) there is no competitive online routing algorithm under the Euclidean distance metric in arbitrary triangulations, and (4) there is no competitive online routing algorithm under the link distance metric even when the input graph is restricted to be a Delaunay, greedy, or minimum-weight triangulation

• 7. Bose, Prosenjit
Luleå tekniska universitet.
Online routing in convex subdivisions2000In: Algorithms and Computation: 11th International Conference, ISAAC 2000 Taipei, Taiwan, December 18-20, 2000 Proceedings / [ed] D.T. Lee; Shang-Hua Teng, Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 2000, p. 47-59Conference paper (Refereed)

We consider online routing algorithms for finding paths between the vertices of plane graphs. We show (1) there exists a routing algorithm for arbitrary triangulations that has no memory and uses no randomization, (2) no equivalent result is possible for convex subdivisions, (3) there is no competitive online routing algorithm under the Euclidean distance metric in arbitrary triangulations, and (4) there is no competitive online routing algorithm under the link distance metric even when the input graph is restricted to be a Delaunay, greedy, or minimum-weight triangulation.

• 8. Brodnik, Andrej
Luleå tekniska universitet.
Sub-linear decoding of Huffman codes almost in-place1998In: Preprint, IMFM , 1998Conference paper (Refereed)

We present a succinct data structure storing the Huffman encoding that permits sublinear decoding in the number of transmitted bits. The size of the extra storage except for the storage of the symbols in the alphabet for the new data structure is O(l log N) bits, where l is the longest Huffman code and N is the number of symbols in the alphabet. We present a solution that typically decodes texts of sizes ranging from a few hundreds up to 68 000 with only one third to one fifth of the number of memory accesses of that of regular Huffman implementations. In our solution, the overhead structure where we do all but one memory access to, is never more than 342 bytes. This will with a very high probability reside in cache, which means that the actual decoding time compares even better

• 9. Brodnik, Andrej
Luleå tekniska universitet. Department of Computer Science, University of Waterloo, Ontario. Department of Computer Science, University of Waterloo, Ontario. Department of Computer Science, Princeton University.
Resizable arrays in optimal time and space1999In: Algorithms and Data Structures: 6th International Workshop, WADS'99 Vancouver, Canada, August 11-14, 1999 Proceedings / [ed] Frank Dehne, Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 1999, p. 37-48Conference paper (Refereed)

We present simple, practical and efficient data structures for the fundamental problem of maintaining a resizable one-dimensional array, A[l..l + n - 1], of fixed-size elements, as elements are added to or removed from one or both ends. Our structures also support access to the element in position i. All operations are performed in constant time. The extra space (i.e., the space used past storing the n current elements) is O(√n) at any point in time. This is shown to be within a constant factor of optimal, even if there are no constraints on the time. If desired, each memory block can be made to have size 2k - c for a specified constant c, and hence the scheme works effectively with the buddy system. The data structures can be used to solve a variety of problems with optimal bounds on time and extra storage. These include stacks, queues, randomized queues, priority queues, and deques.

• 10. Brodnik, Andrej
Blekinge Institute of Technology, Karlskrona. Department of Computer Science, Rutgers University, New Brunswick, NJ. Luleå tekniska universitet. School of Computer Science, University of Waterloo, Waterloo, Ontario.
Worst case constant time priority queue2005In: Journal of Systems and Software, ISSN 0164-1212, E-ISSN 1873-1228, Vol. 78, no 3, p. 249-156Article in journal (Refereed)

We present a new data structure of size 3M bits, where M is the size of the universe at hand, for realizing a discrete priority queue. When this data structure is used in combination with a new memory topology it executes all discrete priority queue operations in O(1) worst case time. In doing so we demonstrate how an unconventional, but practically implementable, memory architecture can be employed to sidestep known lower bounds and achieve constant time performance.

• 11. Brodnik, Andrej
Luleå tekniska universitet. Luleå tekniska universitet. Department of Computer Science, University of Waterloo, Ontario.
Worst case constant time priority queue2001In: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, IEEE Communications Society, 2001, p. 523-528Conference paper (Refereed)

We present a new data structure of size 3M +o(M) bits for solving the "discrete priority queue " problem. When this data structure is used in combination with a new memory topology it provides an O(1) worst case time solution.

• 12. Brodnik, Andrej
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
Interoperability and semantic filtering2006In: Je-LKS: Journal of e-Learning and Knowledge Society, ISSN 1826-6223, E-ISSN 1971-8829, Vol. 2, no 2, p. 165-175Article in journal (Refereed)

Interoperability is often seen only as a technological problem related to reusability. We would like to give interoperability a new role in the structure of the learning environment and in collaborative activities. For us interoperability is also connected with didactical, semiotic and cultural aspects. It improves the interaction between the materials produced with different tools, the construction of kaleidoscopic artifacts and the reﬂ ection on the learning process.

• 13.
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
Bitwise Operations under RAMBO2006Report (Other academic)

In this paper we study the problem of computing w-bit bitwise operations using only O(1) memory probes. We show that under the RAM model there exists a Omega(2^w) space lower bound while under the RAMBO model this space bound goes down to O(w) bits. We present algorithms that use four different RAMBO memory topologies to perform bitwise boolean operations and shift operations.

• 14. Brodnik, Andrej
Luleå tekniska universitet.
Multiprocess time queue2001In: Algorithms and Computation: 12th International Symposium, ISAAC 2001, Christchurch, New Zealand, December 19-21, 2001. / [ed] Peter Eades; Tadao Takaoka, Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 2001, p. 599-609Conference paper (Refereed)

We show how to implement a bounded time queue for two different processes. The time queue is a variant of a priority queue with elements from a discrete universe. The bounded time queue has elements from a discrete bounded universe. One process has time constraints and may only spend constant worst case time on each operation while the other process may spend more time. The time constrained process only has to be able to perform some of the time queue operations while the other process has to be able to perform all operations. We show how to do a deamortization of the deleteMin cost and to provide mutual exclusion for the parts of the data structure that both processes maintain.

• 15.
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science. Faculty of Education, University of Primorska. Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Embedded Internet Systems Lab.
An O(1) solution to the prefix sum problem on a specialized memory architecture2006In: PFourth IFIP International Conference on Theoretical Computer Science - TCS 2006: IFIP 19th World Computer Congress, TC-1, Foundations of Computer Science, August 23-24, 2006, Santiago, Chile / [ed] Gonzalo Navarro; Leopoldo Bertossi; Yoshiharu Kohayakawa, New York: Encyclopedia of Global Archaeology/Springer Verlag, 2006, p. 103-114Conference paper (Refereed)

In this paper we study the Prefix Sum problem introduced by Fredman. We show that it is possible to perform both update and retrieval in O(1) time simultaneously under a memory model in which individual bits may be shared by several words. We also show that two variants (generalizations) of the problem can be solved optimally in Θ(lgN) time under the comparison based model of computation.

• 16. Brodnik, Andrej
BRICS, Centre of the Danish National Research Foundation, University of Aarhus. Department of Computer Science, University of Waterloo, Ontario.
Trans-dichotomous algorithms without multiplication: some upper and lower bounds1997In: Algorithms and Data Structures: 5th International Workshop, WADS'97 Halifax, Nova Scotia, Canada August 6-8, 1997 Proceedings / [ed] Frank Dehne; Andrew Rau-Chaplin; Jörg-Rüdiger Sack; Roberto Tamassia, Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 1997, p. 426-439Conference paper (Refereed)

We show that on a RAM with addition, subtraction, bitwise Boolean operations and shifts, but no multiplication, there is a transdichotomous solution to the static dictionary problem using linear space and with query time log n(log log n)1+0(1). On the way, we show that two w-bit words can be multiplied in time (log w)1+0(1) and that time (log w) is necessary, and that (log log w) time is necessary and sufficient for identifying the least significant set bit of a word.

• 17. Brodnik, Andrej
Membership in constant time and almost-minimum space1999In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 28, no 5, p. 1627-1640Article in journal (Refereed)

This paper deals with the problem of storing a subset of elements from the bounded universe $\mathcal{M} = \{0, \ldots, M-1\}$ so that membership queries can be performed efficiently. In particular, we introduce a data structure to represent a subset of $N$ elements of $\mathcal{M}$ in a number of bits close to the information-theoretic minimum, $B = \left\lceil \lg {M\choose N} \right\rceil$, and use the structure to answer membership queries in constant time.

• 18.
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
University of Waterloo, Ontario.
Neighbours on a grid1996In: Algorithm Theory - SWAT'96: Proceedings of the 5th Scandinavian Workshop on Algorithm Theory / [ed] R. Karlsson; Andrzej Lingas, Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 1996, p. 309-320Conference paper (Refereed)
• 19. Brodnik, Andrej
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Embedded Internet Systems Lab.
A static data structure for discrete advance bandwidth reservations on the Internet2003In: Proceedings of Swedish National Computer Networking Workshop: SNCNW 2003, Stockholm, 2003Conference paper (Refereed)
• 20. Brodnik, Andrej
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Embedded Internet Systems Lab.
An efficient data structure for advance bandwidth reservations on the Internet2002In: Proceedings of CSEE 2002: Second Annual Conference on Computer Science and Electrical Engineering. The third Annual Symposium on Computer Science and Electrical Engineering, 2002Conference paper (Refereed)

In this contribution we present a problem of resource reservation during some time. We show that the problem has a lower bound of Ω (log n) per operation on average and also give a matching upper bound algorithm.

• 21. Brodnik, Andrej
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Embedded Internet Systems Lab.
Data structure for a time-based bandwidth reservations problem2003Report (Other academic)

We discuss a problem of handling resource reservations. The resource can be reserved for some time, it can be freed or it can be queried what is the largest amount of reserved resource during a time interval. We show that the problem has a lower bound of $\Omega(\log n)$ per operation on average and we give a matching upper bound algorithm. Our solution also solves a dynamic version of the related problems of a prefix sum and a partial sum.

• 22. Brodnik, Andrej
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Embedded Internet Systems Lab.
Static data structure for discrete advance bandwidth reservations on the internet2003Report (Other academic)

In this paper we present a discrete data structure for reservations of limited resources. A reservation is defined as a tuple consisting of the time interval of when the resource should be reserved, $I_R$, and the amount of the resource that is reserved, $B_R$, formally $R=\{I_R,B_R\}$. The data structure is similar to a segment tree. The maximum spanning interval of the data structure is fixed and defined in advance. The granularity and thereby the size of the intervals of the leaves is also defined in advance. The data structure is built only once. Neither nodes nor leaves are ever inserted, deleted or moved. Hence, the running time of the operations does not depend on the number of reservations previously made. The running time does not depend on the size of the interval of the reservation either. Let $n$ be the number of leaves in the data structure. In the worst case, the number of touched (i.e. traversed) nodes is in any operation $O(\log n)$, hence the running time of any operation is also $O(\log n)$.

• 23.
Luleå tekniska universitet.
Luleå tekniska universitet. Luleå University of Technology.
Small forwarding tables for fast routing lookups1997In: Computer communication review, ISSN 0146-4833, E-ISSN 1943-5819, Vol. 27, no 4, p. 3-14Article in journal (Refereed)

For some time, the networking community has assumed that it is impossible to do IP routing lookups in software fast enough to support gigabit speeds. IP routing lookups must find the routing entry with the longest matching prefix, a task that has been thought to require hardware support at lookup frequencies of millions per second.We present a forwarding table data structure designed for quick routing lookups. Forwarding tables are small enough to fit in the cache of a conventional general purpose processor. With the table in cache, a 200 MHz Pentium Pro or a 333 MHz Alpha 21164 can perform a few million lookups per second. This means that it is feasible to do a full routing lookup for each IP packet at gigabit speeds without special hardware.The forwarding tables are very small, a large routing table with 40,000 routing entries can be compacted to a forwarding table of 150-160 Kbytes. A lookup typically requires less than 100 instructions on an Alpha, using eight memory references accessing a total of 14 bytes.

• 24.
Luleå tekniska universitet.
Luleå tekniska universitet. Luleå University of Technology.
Small forwarding tables for fast routing lookups1997Report (Other academic)

For some time, the Internet community has believed that it is impossible to do IP routing lookups in software fast enough to support gigabit speeds. IP routing lookups must find the routing entry with the longest matching prefix, a task that has been thought to require hardware support at lookup frequencies of millions per second. We present a forwarding table data structure designed for quick routing lookups. Forwarding tables are small enough to fit in the cache of a conventional general purpose processor. With the table in cache, a 200 MHz Pentium Pro or a 333 MHz Alpha 21164 can perform a few million lookups per second. This means that it is feasible to do a full routing lookup for each IP packet at gigabit speeds without special hardware. The forwarding tables are very small, a large routing table with 40,000 routing entries can be compacted to a forwarding table of 150--160 Kbytes. A lookup typically requires less than 100 instructions on an Alpha, using eight memory references accessing a total of 14 bytes.

• 25.
Luleå tekniska universitet.
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science. Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Embedded Internet Systems Lab. Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
Extended expedited forwarding: the in-time PHB group2003In: Computers and Communication, 2003. (ISCC 2003): Proceedings of the Eighth IEEE International Symposium on Computers and Communications, IEEE Computer Society Press , 2003, Vol. 1, p. 291-298Conference paper (Refereed)

This paper presents a new set of forwarding behaviorsthat fits rate-adaptive and delay-sensitive applications withlimited loss tolerance. We consider an application to havelimited loss tolerance if it needs loss-free forwarding of specificpackets up to a certain rate. The new set of forwardingbehaviors are attractive for developing real-time applicationsfor the Internet. In particular, such applications canbe designed to use reserved forwarding capacity efficientlyand compete for more bandwidth while being fair to best-efforttraffic. To provide the new set of forwarding behaviors,we define a scheduling mechanism that can be implementedefficiently. Through simulations, we show that thismechanism supports the defined forwarding behaviors.

• 26.
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
University of Ljubljana, Faculty of Computer and Information Science. Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science. University of Ljubljana, Faculty of Computer and Information Science.
Reality considerations when designing a TDMA-FDMA based link-layer for real-time WSN2012In: Multiple Access Communications: 5th International Workshop, MACOM 2012, Maynooth, Ireland, November 19-20, 2012. Proceedings / [ed] Boris Bellalta, Encyclopedia of Global Archaeology/Springer Verlag, 2012, p. 93-96Conference paper (Refereed)

In this article we elaborate on reality considerations when deploying wireless sensor networks with strict end-to-end delay requirement. Our improvements are particularly important for a design and implementation of strict real-time systems while at the same time we decrease overall power consumption. Firstly, we design and implement application tailored TDMA-FDMA medium access protocol with guaranteed end-to-end delay. Secondly, we integrate in the implementation of the protocol the bootstrapping mechanism and thirdly, the time synchronization mechanism. Next, we show that by combining medium access protocol, bootstrapping, and time synchronization mechanisms within the link-layer, we can limit on average clock drift in the network to 0.5 micro seconds, as well as achieve 81 % energy efficiency while keeping collision probability at its minimum of 1 %. Finally, we conclude with challenges and lessons learned in real-world deployment of TDMA/FDMA based link-layer with guaranteed end-to-end delay in wireless sensor networks.

1 - 26 of 26
Cite
Citation style
• apa
• ieee
• modern-language-association-8th-edition
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf