waashk/dblp huggingface dataset:
efficient algorithms for two generalized 2-median problems and the group median problem on trees. the p-median problem on a tree t is to find a set s of p vertices on that minimizes the sum of distances from t's vertices to s. in this paper, we study two generalizations of the 2-median problem, which are obtained by imposing constraints on the two vertices selected as a 2-median: one is to limit their distance while the other is to limit their eccentricity. previously, both the best upper bounds of these two generalizations were o(n2) [a. tamir, d. perez-brito, j.a. moreno-perez, a polynomial algorithm for the p-centdian problem on a tree, networks 32 (1998) 255-262; b.-f. wang, s.-c. ku, k.-h. shi, cost-optimal parallel algorithms for the tree bisector problem and applications, ieee transactions on parallel and distributed systems 12 (9) (2001) 888-898]. in this paper, we solve both in o(nlogn) time. we also study cases when linear time algorithms exist for the two generalizations. for example, we solve both in linear time when edge lengths and vertex weights are all polynomially bounded integers. furthermore, we consider the relaxation of the two generalized problems by allowing 2-medians on any position of edges, instead of just on vertices, and we give o(nlogn)-time algorithms for them. a problem, named the tree marker problem, arises several times in our approaches to the two generalized 2-median problems, and we give an o(nlogn)-time algorithm for this problem. we also use this algorithm to speedup an algorithm of gupta and punnen [s.k. gupta, a.p. punnen, group center and group median of a tree, european journal of operational research 65 (1993) 400-406] for the group median problem, improving the running time from o(kn) to o(n+klogn), where k is the number of groups in the input.
rapid almost-complete broadcasting in faulty networks. this paper studies the problem of broadcasting in synchronous point-to-point networks, where one initiator owns a piece of information that has to be transmitted to all other vertices as fast as possible. the model of fractional dynamic faults with threshold is considered: in every step either a fixed number c(g)-1, where c(g) is the edge connectivity of the communication graph, or a fraction @a of sent messages can be lost depending on which quantity is larger. as the main result we show that in complete graphs and hypercubes it is possible to inform all but a constant number of vertices, exhibiting only a logarithmic slowdown, i.e. in time o(dlogn) where d is the diameter of the network and n is the number of vertices. moreover, for complete graphs under some additional conditions (sense of direction, or @a
what does it mean to say that a physical system implements a computation? when we are concerned with the logical form of a computation and its formal properties, then it can be theoretically described in terms of mathematical and logical functions and relations between abstract entities. however, actual computation is realised by some physical process, and the latter is of course subject to physical laws and the laws of thermodynamics in particular. an issue that has been the subject of much controversy is that of whether or not there are any systematic connections between the logical properties of computations considered abstractly and the thermodynamical properties of their concrete physical realizations. landauer [r. landauer, irreversibility and heat generation in the computing process, ibm journal of research and development 5 (1961) 183-191. reprinted in leff and rex (1990)] proposed such a general connection, known as landauer's principle. to resolve this matter an analysis of the notion of the implementation of a computation by a physical system is clearly required. another issue that calls for an analysis of implementation is that of realism about computation. the account of implementation presented here is based on the notion of an l-machine. this is a hybrid physical-logical entity that combines a physical device, a specification of which physical states of that device correspond to various logical states, and an evolution of that device which corresponds to the logical transformation l. the most general form of landauer's principle can be precisely stated in terms of l-machines, namely that the logical irreversibility of l implies the thermodynamic irreversibility of every corresponding l-machine.
an approximation algorithm to the k-steiner forest problem. given a graph g, an integer k, and a demand set d={(s"1,t"1),...,(s"l,t"l)}, the k-steiner forest problem finds a forest in graph g to connect at least k demands in d such that the cost of the forest is minimized. this problem was proposed by hajiaghayi and jain in soda'06. thereafter, using a lagrangian relaxation technique, segev et al. gave the first approximation algorithm to this problem in esa'06, with performance ratio o(n^2^/^3logl). we give a simpler and faster approximation algorithm to this problem with performance ratio o(n^2^/^3logk) via greedy approach, improving the previously best known ratio in the literature.
empire of colonies: self-stabilizing and self-organizing distributed algorithm. self-stabilization ensures automatic recovery from an arbitrary state; we define self-organization as a property of algorithms which display local attributes. more precisely, we say that an algorithm is self-organizing if (1) it converges in sublinear time and (2) reacts ''fast'' to topology changes. if s(n) is an upper bound on the convergence time and d(n) is an upper bound on the convergence time following a topology change, then s(n)@?o(n) and d(n)@?o(s(n)). the self-organization property can then be used for gaining, in sub-linear time, global properties and reaction to changes. we present self-stabilizing and self-organizing algorithms for many distributed algorithms, including distributed snapshot and leader election. we present a new randomized self-stabilizing distributed algorithm for cluster definition in communication graphs of bounded degree processors. these graphs reflect sensor networks deployment. the algorithm converges in o(logn) expected number of rounds, handles dynamic changes locally and is, therefore, self-organizing. applying the clustering algorithm to specific classes of communication graphs, in o(logn) levels, using an overlay network abstraction, results in a self-stabilizing and self-organizing distributed algorithm for hierarchy definition. given the obtained hierarchy definition, we present an algorithm for hierarchical distributed snapshots. the algorithms are based on a new basic snap-stabilizing snapshot algorithm, designed for message passing systems in which a distributed spanning tree is defined and in which processors communicate using bounded links capacity. the algorithm is on-demand self-stabilizing when no such distributed spanning tree is defined. namely, it stabilizes regardless of the number of snapshot invocations. the combination of the self-stabilizing and self-organizing distributed hierarchy construction and the snapshot algorithm forms an efficient self-stabilizer transformer. given a distributed algorithm for a specific task, we are able to convert the algorithm into a self-stabilizing algorithm for the same task with an expected convergence time of o(log^2n) rounds.
the consequence relation in the logic of commutative gbl-algebras is pspace-complete. commutative, integral and bounded gbl-algebras form a subvariety of residuated lattices which provides the algebraic semantics of an interesting common fragment of intuitionistic logic and of several fuzzy logics. it is known that both the equational theory and the quasiequational theory of commutative gbl-algebras are decidable (in contrast to the noncommutative case), but their complexity has not been studied yet. in this paper, we prove that both theories are in pspace, and that the quasiequational theory is pspace-hard.
from adaptive renaming to set agreement. the adaptive m-renaming problem consists of providing processes with a new name taken from a name space whose size m depends only on the number p of processes that participate in the renaming (and not on the total number n of processes that could ask for a new name). the k-set agreement problem allows each process that proposes a value to decide a proposed value in such a way that at most k different values are decided. in an asynchronous system prone to up to t process crash failures, and where processes can cooperate by accessing atomic read/write registers only, the best that can be done is a renaming space of size m=p+t. in the same setting, the k-set agreement problem cannot be solved when t>=k. this paper focuses on the way a solution to the adaptive renaming problem can help in solving the k-set agreement problem when t>=k. it has two contributions. considering the case k=t (1@?t2k (i.e. adaptive (p+k-1)-renaming allows progressing from k>t to k=t, but does not allow bypassing the ''k=t'' frontier when n>2k).
probabilistic mobile ambients. the calculus of mobile ambients has been introduced for expressing mobility and mobile computation. in this paper we present a probabilistic version of mobile ambients by augmenting the syntax of the original ambient calculus with a (guarded) probabilistic choice operator. to allow for the representation of both the probabilistic behaviour introduced through the new probabilistic choice operator and the nondeterminism present in the original ambient calculus we use probabilistic automata as the underpinning semantic model. the ambient logic is a logic for mobile ambients that contains a novel treatment of both locations and hidden names. for specifying properties of probabilistic mobile ambients, we extend this logic to specify probabilistic behaviour. in addition, to show the utility of our approach we present an example of a virus infecting a network.
hascasl: integrated higher-order specification and program development. we lay out the design of hascasl, a higher order extension of the algebraic specification language casl that serves both as a wide-spectrum language for the rigorous specification and development of software, in particular but not exclusively in modern functional programming languages, and as an expressive standard language for higher-order logic. distinctive features of hascasl include partial higher order functions, higher order subtyping, shallow polymorphism, and an extensive type-class mechanism. moreover, hascasl provides dedicated specification support for monad-based functional-imperative programming with generic side effects, including a monad-based generic hoare logic.
single machine parallel-batch scheduling with deteriorating jobs. we consider several single machine parallel-batch scheduling problems in which the processing time of a job is a linear function of its starting time. we give a polynomial-time algorithm for minimizing the maximum cost, an o(n5) time algorithm for minimizing the number of tardy jobs, and an o(n2) time algorithm for minimizing the total weighted completion time. furthermore, we prove that the problem for minimizing the weighted number of tardy jobs is binary np-hard.
two improved range-efficient algorithms for f estimation. we present two new algorithms for the range-efficient f"0 estimating problem and improve the previously best known result, proposed by pavan and tirthapura in 2005. furthermore, our algorithms can be applied to improve the previously best known result for the max-dominance norm problem.
a variant of the tandem duplication - random loss model of genome rearrangement. in [k. chaudhuri, k. chen, r. mihaescu, s. rao, on the tandem duplication-random loss model of genome rearrangement, in: soda, 2006, pp. 564-570], chaudhuri, chen, mihaescu and rao study algorithmic properties of the tandem duplication - random loss model of genome rearrangement, well-known in evolutionary biology. in their model, the cost of one step of duplication-loss of width k is &alpha;k for &alpha;=1 or &alpha;&ge;2. in this paper, we study a variant of this model, where the cost of one step of width k is 1 if k&le;k and &infin; if k>k, for any value of the parameter k&epsilon;ℕ&cup;{&infin;}. we first show that permutations obtained after p steps of width k define classes of pattern-avoiding permutations. we also compute the numbers of duplication-loss steps of width k necessary and sufficient to obtain any permutation of sn, in the worst case and on average. in this second part, we may also consider the case k=k(n), a function of the size n of the permutation on which the duplication-loss operations are performed.
computational virtuality in biological systems. computational virtuality is introduced as a key distinguishing feature of genuinely computational systems. evidence is provided that the basic cellular machinery possesses virtuality. accordingly, one can step beyond the commonplace metaphor of computation as applied to molecular biology, and come to view the cell as a genuine computing system. the human nervous system is analyzed in the same light, setting an agenda for research on virtuality in recurrent neural networks, whose outcomes in the way of theoretical results and simulation of biological neural systems may heuristically guide neuroscientists in the search for virtual computing in the brain.
two complementary operations inspired by the dna hairpin formation: completion and reduction. we consider two complementary operations: hairpin completion introduced in [d. cheptea, c. martin-vide, v. mitrana, a new operation on words suggested by dna biochemistry: hairpin completion, in: proc. transgressive computing, 2006, pp. 216-228] with motivations coming from dna biochemistry and hairpin reduction as the inverse operation of the hairpin completion. both operations are viewed here as formal operations on words and languages. we settle the closure properties of the classes of regular and linear context-free languages under hairpin completion in comparison with hairpin reduction. while the class of linear context-free languages is exactly the weak-code image of the class of the hairpin completion of regular languages, rather surprisingly, the weak-code image of the class of the hairpin completion of linear context-free languages is a class of mildly context-sensitive languages. the closure properties with respect to the hairpin reduction of some time and space complexity classes are also studied. we show that the factors found in the general cases are not necessary for regular and context-free languages. this part of the paper completes the results given in the earlier paper, where a similar investigation was made for hairpin completion. finally, we briefly discuss the iterated variants of these operations.
improved approximation bounds for edge dominating set in dense graphs. we analyze the simple greedy algorithm that iteratively removes the endpoints of a maximum-degree edge in a graph, where the degree of an edge is the sum of the degrees of its endpoints. this algorithm provides a 2-approximation to the minimum edge dominating set and minimum maximal matching problems. we refine its analysis and give an expression of the approximation ratio that is strictly less than 2 in the cases where the input graph has n vertices and at least @e(n2) edges, for @e>1/2. this ratio is shown to be asymptotically tight for @e>1/2.
hop chains: secure routing and the establishment of distinct identities. we present a secure routing protocol that is immune to sybil attacks and that can tolerate collusion of byzantine routers. it can tolerate either initial collusion of byzantine routers or runtime collusion of non-adjacent byzantine routers, both in the absence of runtime collusion between adjacent routers. for these settings, the calculated distance from a destination to a node is not smaller than the actual shortest distance from the destination to the node. the protocol can also simultaneously tolerate initial collusion of byzantine routers and runtime collusion of adjacent byzantine routers but in the absence of runtime collusion between non-adjacent routers. for this setting, it guarantees a bound on the difference between the calculated distance and the actual shortest distance. the bound depends on the number of byzantine routers on a path. the protocol makes very weak timing assumptions and requires synchronization only between neighbors or second neighbors. we propose to use this protocol for secure localization of routers using hop-count distances, which can be then used as a proof of identity of nodes.
nadia busi (1968-2007). nadia busi obtained a master in computer science in 1993, at the university of bologna. in 1997 she obtained a phd in theoretical computer science at the university of siena; her thesis entitled "petri nets with inhibitor and read arcs: semantics, analysis and application to process calculi" won the annual prize of the italian chapter of eatcs for the best italian phd thesis.the scientific activity of nadia was very broad, and covered different aspects of theoretical computer science. her first interests concerned the investigation of expressiveness problems in concurrency theory. in collaboration with roberto gorrieri and gianluigi zavattaro, she studied primitive nets, a subclass of petri nets with inhibitor arcs, investigating various decidable properties of such nets. she also studied different properties of various process calculi, by mapping them on primitive nets.
computing on a partially eponymous ring. we study the partially eponymous model of distributed computation, which simultaneously generalizes the anonymous and the eponymous models. in this model, processors have identities, which are neither necessarily all identical (as in the anonymous model) nor necessarily unique (as in the eponymous model). in a decision problem formalized as a relation, processors receive inputs and seek to reach outputs respecting the relation. we focus on the partially eponymous ring, and we shall consider the computation of circularly symmetric relations on it. we consider sets of rings where all rings in the set have the same multiset of identity multiplicities. *we distinguish between solvability and computability: in solvability, processors are required to always reach outputs respecting the relation; in computability, they must do so whenever this is possible, and must otherwise report impossibility. -we present a topological characterization of solvability for a relation on a set of rings, which can be expressed as an efficiently checkable, number-theoretic predicate. -we present a universal distributed algorithm for computing a relation on a set of rings; it runs any distributed algorithm for constructing views, followed by local steps. *we derive, as our main result, a universal upper bound on the message complexity to compute a relation on a set of rings; this bound demonstrates a graceful degradation with the least minimum base, a parameter indicating the degree of least possible eponymity for a set of rings. thereafter, we identify two cases where a relation can be computed on a set of rings, with rings of size n, with an efficient number of o(n@?lgn) messages.
how liquid is biological signalling? this paper proposes an investigation of the global statistics of synthetic protein networks-a step towards a systemic understanding of their design space. we derive a liquidity index which describes the onset of the phase transition where an ensemble of agents aggregates into a giant cluster. this index captures the influence of both the domain distribution of agents and the binding strengths of their various domains in the limit of infinite populations. in simple cases it is possible to derive an explicit analytical expression of this index, which allows one to compare with simulations, and get a sense of how it transfers to the concrete finite case.
constructing edge-disjoint spanning trees in locally twisted cubes. the use of edge-disjoint spanning trees for data broadcasting and scattering problem in networks provides a number of advantages, including the increase of bandwidth and fault-tolerance. in this paper, we present an algorithm for constructing n edge-disjoint spanning trees in an n-dimensional locally twisted cube. since the n-dimensional locally twisted cube is regular with the common degree n, the number of constructed trees is optimal.
upper bounds and algorithms for parallel knock-out numbers. we study parallel knock-out schemes for graphs. these schemes proceed in rounds in each of which each surviving vertex simultaneously eliminates one of its surviving neighbours; a graph is reducible if such a scheme can eliminate every vertex in the graph. we resolve the square-root conjecture, first posed at mfcs 2004, by showing that for a reducible graph g, the minimum number of required rounds is o(n); in fact, our result is stronger than the conjecture as we show that the minimum number of required rounds is o(@a), where @a is the independence number of g. this upper bound is tight. we also show that for reducible k"1","p-free graphs at most p-1 rounds are required. it is already known that the problem of whether a given graph is reducible is np-complete. for claw-free graphs, however, we show that this problem can be solved in polynomial time. we also pinpoint a relationship with (locally bijective) graph homomorphisms.
a study of substitution, using nominal techniques and fraenkel-mostowksi sets. fraenkel-mostowski (fm) set theory delivers a model of names and alpha-equivalence. this model, now generally called the 'nominal' model, delivers inductive datatypes of syntax with alpha-equivalence - rather than inductive datatypes of syntax, quotiented by alpha-equivalence. the treatment of names and alpha-equivalence extends to the entire sets universe. this has proven useful for developing 'nominal' theories of reasoning and programming on syntax with alpha-equivalence, because a sets universe includes elements representing functions, predicates, and behaviour. often, we want names and alpha-equivalence to model capture-avoiding substitution. in this paper we show that fm set theory models capture-avoiding substitution for names in much the same way as it models alpha-equivalence; as an operation valid for the entire sets universe which coincides with the usual (inductively defined) operation on inductive datatypes. in fact, more than one substitution action is possible (they all agree on sets representing syntax). we present two distinct substitution actions, making no judgement as to which one is 'right' - we suspect this question has the same status as asking whether classical or intuitionistic logic is 'right'. we describe the actions in detail, and describe the overall design issues involved in creating any substitution action on a sets universe. along the way, we think in new ways about the structure of elements of fm set theory. this leads us to some interesting mathematical concepts, including the notions of planes and crucial elements, which we also describe in detail.
fault-free longest paths in star networks with conditional link faults. the star network, which belongs to the class of cayley graphs, is one of the most versatile interconnection networks for parallel and distributed computing. in this paper, adopting the conditional fault model in which each node is assumed to be incident with two or more fault-free links, we show that an n-dimensional star network can tolerate up to 2n-7 link faults, and be strongly (fault-free) hamiltonian laceable, where n>=4. in other words, we can embed a fault-free linear array of length n!-1 (n!-2) in an n-dimensional star network with up to 2n-7 link faults, if the two end nodes belong to different partite sets (the same partite set). the result is optimal with respect to the number of link faults tolerated. it is already known that under the random fault model, an n-dimensional star network can tolerate up to n-3 faulty links and be strongly hamiltonian laceable, for n>=3.