38894685
A Strongly Polynomial Algorithm for the Inverse Shortest Arborescence Problem
Abstract In this paper an inverse problem of the weighted shortest arborescence problem is discussed. That is, given a directed graph G and a set of nonnegative costs on its arcs, we need to modify those costs as little as possible to ensure that T, a given v1 -arborescence of G, is the shortest one. It is found that only the cost of T needs modifying. An O(n3) combinatorial algorithm is then proposed. This algorithm also gives an optimal solution to the inverse weighted shortest path problem.
42940477
Hamiltonian iterated line graphs
The n-iterated line graph of a graph G is Ln(G) = L(Ln-1(G)), where L1(G) denotes the line graph L(G) of G, and Ln-1(G) is assumed to be nonempty. Harary and Nash-Williams characterized those graphs G for which L(G) is hamiltonian. In this paper, we will give a characterization of those graphs G for which Ln(G) is hamiltonian, for each n ≥ 2. This is not a simple consequence of Harary and Nash-Williams' result. As an application, we show two methods for determining the hamiltonian index of a graph and enhance various results on the hamiltonian index known earlier.
3399031
On 2-factors in claw-free graphs
Abstract A graph is said claw-free if it contains no induced subgraph isomorphic to K 1,3 . We prove that if G is a claw-free graph with minimum degree δ ⩾4, then G contains a 2-factor with at most 6 n /( δ +2)−1 components. Moreover, together with a theorem of Choudoum and Paulraj (J. Graph Theory 15 (1991) 259–265) and one of Anstee (J. Algorithms 6 (1985) 112–131), it is polynomial (in O( n 3 )) to construct such a 2-factor.
11711500
Verification of schedulability for real-time programs
Assume that a real-time programPT consisting of a number of parallel processes is executed on a system having a setPr of processors which are shared between the processes by a real-time schedulerST. Assume that PT must meet some timing deadlines. We show that such an implementation ofPT can be represented as a transformationL(PT) and that the deadlines ofPT will be met if they are satisfied by the timing properties of the transformed program. The condition for feasibility of a real-time program executed under a scheduler is formalized and rules are provided for verification. The schedulerST can be specifiedgenerically and applied to different programs, making it unnecessary to introduce low-level operations such as scheduling primitives into the programming language. Thus real-time program specification and Schedulability can be considered in the same framework and the timing properties of a program can be determined at the specification level. By separating the specification of the scheduler from that of the program, the feasibility of an implementation can be proved by considering a scheduling policy rather than its implementation details.
6908345
A swarm intelligence routing algorithm for MANETs
This paper presents a novel swarm intelligence inspired routing algorithm (EARA) for mobile ad hoc networks. Based on the understanding of the evolutionary cooperation in the biological swarm, which provides an alternative solution resilient against changes in the dynamic environment, We use the principle of swarm intelligence for the reinforcement of optimal routes with only local communication (here, local communication is defined as neighbourto-neighbour one only). The data traffic is influenced at each node, and the communicating nodes observe this influence to update their tables. We also include an evaluation, and the simulation results show that this routing algorithm scales well to a variety of network conditions.
17193716
Detecting news reporting using audio/visual information
This paper proposes an integrated approach to discriminate news reporting from everything else in broadcast news data based on both audio and visual information. The separation of news reporting segments from others not only can provide useful indices for video streams but also serves as a pre-processing step for tasks such as speaker identification and speech recognition so that only speech segments are passed on for further processing. A set of audio and visual features are adopted that aim at capturing the intrinsic properties of the underlying classes. Four types of classifiers (threshold fuzzy, Gaussian Mixture Model based, and Support Vector Machine) are tested. Some of the experimental results are presented and discussed in the paper.
3761715
A multicommodity flow model for distributed stream processing
The rapid development of computer technology has enabled streaming applications to emerge from many areas of the IT industry. A fundamental problem in such stream processing systems is how to best utilize the available resources so that the overall system performance is optimized. In most real time systems, applications are often running in a decentralized, distributed environment. At any given time, no server has the global information about all the servers in the system. It is thus desirable to have distributed solutions capable of adapting to or absorbing local changes in production rates and in network conditions. This paper addresses the fundamental resource allocation question in the distributed stream processing setting. Specifically, we consider a generic model for stream processing systems. Each stream is required to complete a series of tasks to become finished product. Each server is responsible for a subset of the processing tasks for possibly a subset of the streams. All servers have finite computing resources and all communication links have finite available bandwidth. We consider the resource allocation problem so as to maximize the total throughput of the system. Our problem can be described as a generalization of the traditional multicommodity flow problem [1]. Traditional multicommodity flow problem looks for the best way to use of the link capacities to deliver the maximum throughput for the flows in the whole network. In our problem, in addition to the link bandwidth constraints, we also have processing power constraints for each server. Furthermore, we allow flow shrinkage or expansion so as to model operations such
774892
Single Machine Scheduling Subject To Precedence Delays
Abstract A single-machine scheduling problem with precedence delays is analyzed. A set of n tasks is to be scheduled on the machine in such a way that the makespan is minimized. The executions of the tasks are constrained by precedence delays, i.e., a task can start its execution only after any of its predecessors has completed and the delay between the two tasks has elapsed. In the case of unit execution times and integer lengths of delays, the problem is shown to be NP-hard in the strong sense. In the case of integer execution times and unit length of delays, the problem is polynomial, and an O(n2) optimal algorithm is provided. Both preemptive and non-preemptive cases are considered.