Department of Algorithms and Systems Modelling - Administrative Units - Bridge of Knowledge

Search

Department of Algorithms and Systems Modelling

Filters

total: 513

  • Category
  • Year
  • Options

clear Chosen catalog filters disabled

Catalog Publications

Year 2013
  • Optimal edge-coloring with edge rate constraints
    Publication

    - NETWORKS - Year 2013

    We consider the problem of covering the edges of a graph by a sequence of matchings subject to the constraint that each edge e appears in at least a given fraction r(e) of the matchings. Although it can be determined in polynomial time whether such a sequence of matchings exists or not [Grötschel et al., Combinatorica (1981), 169–197], we show that several questions about the length of the sequence are computationally intractable....

    Full text to download in external service

  • Partial dominated schedules and minimizing the total completion time of deteriorating jobs
    Publication

    A problem of scheduling deteriorating jobs on a single processor is considered. The processing time of a job is given by a function pi=ai+bisi, where si is the starting time of the job, ai>=0, bi>=0, for i=1,...,n. Jobs are non-preemptive and independent and there are neither ready times nor deadlines. The goal is to minimize the total weighted completion time. We show how to employ the concept of non-dominated schedules to construct...

    Full text to download in external service

  • Robustness of quantum-randomness expansion protocols in the presence of noise
    Publication

    - PHYSICAL REVIEW A - Year 2013

    In this paper we investigate properties of several randomness generation protocols in the device independent framework. Using Bell-type inequalities it is possible to certify that the numbers generated by an untrusted device are indeed random. We present a selection of certificates which guarantee two bits of randomness for each run of the experiment in the noiseless case and require the parties to share a maximally entangled state....

    Full text available to download

  • Three-fast-searchable graphs
    Publication

    - DISCRETE APPLIED MATHEMATICS - Year 2013

    In the edge searching problem, searchers move from vertex to vertex in a graph to capture an invisible, fast intruder that may occupy either vertices or edges. Fast searching is a monotonic internal model in which, at every move, a new edge of the graph G must be guaranteed to be free of the intruder. That is, once all searchers are placed the graph G is cleared in exactly |E(G)| moves. Such a restriction obviously necessitates...

    Full text available to download

  • Trees having many minimal dominating sets

    We provide an algorithm for listing all minimal dominating sets of a tree of order n in time O(1.4656^n). This leads to that every tree has at most 1.4656^n minimal dominating sets. We also give an infinite family of trees of odd and even order for which the number of minimal dominating sets exceeds 1.4167^n, thus exceeding 2^{n/2}. This establishes a lower bound on the running time of an algorithm for listing all minimal dominating...

    Full text to download in external service

  • Zero-Visibility Cops and Robber Game on a Graph
    Publication

    - LECTURE NOTES IN COMPUTER SCIENCE - Year 2013

    We examine the zero-visibility cops and robber graph searching model, which differs from the classical cops & robber game in one way: the robber is invisible. We show that this model is not monotonic. We also provide bounds on both the zero-visibility copnumber and monotonic zero-visibility copnumber in terms of the pathwidth.

    Full text to download in external service

Year 2012
Year 2011