waashk/dblp huggingface dataset:
parallel computation in spiking neural nets. numerical quantities can be represented as phase differences between equiperiodic oscillating subsystems in a spiking neural net. it is then possible to represent integer variables, and the increment and decrement operations, x:=x+1, x:=x-1. it is possible to represent the if construction, the while construction, and some other programming language constructions, including variants of the seq, par, and alt constructors, which were used in occam. we give a general purpose parallel programming language with integer variables which can be systematically implemented in spiking neural networks. addition, subtraction and multiplication are done, albeit inefficiently, as examples.
on the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs. golumbic, kaplan, and shamir, in their paper [m.c. golumbic, h. kaplan, r. shamir, graph sandwich problems, j. algorithms 19 (1995) 449-473] on graph sandwich problems published in 1995, left the status of sandwich problems for strongly chordal graphs and chordal bipartite graphs open. we prove that the sandwich problem for strongly chordal graphs is np-complete. we also give some comments on the computational complexity of the sandwich problem for chordal bipartite graphs.
on the fairness and complexity of generalized k-in-a-row games. recently, wu and huang [i.-c. wu, d.-y. huang, a new family of k-in-a-row games, in: the 11th advances in computer games conference, acg'11, taipei, taiwan, september 2005] introduced a new game called connect6, where two players, black and white, alternately place two stones of their own color, black and white respectively, on an empty go-like board, except for that black (the first player) places one stone only for the first move. the one who gets six consecutive (horizontally, vertically or diagonally) stones of his color first wins the game. unlike go-moku, connect6 appears to be fairer and has been adopted as an official competition event in computer olympiad 2006. connect(m,n,k,p,q) is a generalized family of k-in-a-row games, where two players place p stones on an mxn board alternatively, except black places q stones in the first move. the one who first gets his stones k-consecutive in a line (horizontally, vertically or diagonally) wins. connect6 is simply the game of connect(m,n,6,2,1). in this paper, we study two interesting issues of connect(m,n,k,p,q): fairness and complexity. first, we prove that no one has a winning strategy in connect(m,n,k,p,q) starting from an empty board when k>=4p+7 and p>=q. second, we prove that, for any fixed constants k,p such that k-p>=max{3,p} and a given connect(m,n,k,p,q) position, it is pspace-complete to determine whether the first player has a winning strategy. consequently, this implies that connect6 played on an mxn board (i.e., connect(m,n,6,2,1)) is pspace-complete.
path constraints in semistructured data. we consider semistructured data as multirooted edge-labelled directed graphs, and path inclusion constraints on these graphs. a path inclusion constraint p@?q is satisfied by a semistructured data if any node reached by the regular query p is also reached by the regular query q. in this paper, two problems are mainly studied: the implication problem and the problem of the existence of a finite exact model. -we give a new decision algorithm for the implication problem of a constraint p@?q by a set of bounded path constraints p"i@?u"i where p, q, and the p"i's are regular path expressions and the u"i's are words, improving in this particular case, the more general algorithms of s. abiteboul and v. vianu, and n. alechina et al. in the case of a set of word equalities u"i=v"i, we provide a more efficient decision algorithm for the implication of a word equality u=v, improving the more general algorithm of p. buneman et al. we prove that, in this case, implication for nondeterministic models is equivalent to implication for (complete) deterministic ones. -we introduce the notion of exact model: an exact model of a set of path constraints c satisfies the constraint p@?q if and only if this constraint is implied by c. we prove that any set of constraints has an exact model and we give a decidable characterization of data which are exact models of bounded path inclusion constraints sets.
compressing table data with column dependency. tables are two-dimensional arrays given in row-major order. such data have unique features that could be exploited for effective compression. for example, tables often represent database files with rows as records so certain columns or fields in a table may have few distinct values. this means that simply transposing the data can make it compress better. further, a large source of information redundancy in a table is the correlation among columns representing related types of data. this paper formalizes the notion of column dependency as a way to capture this information redundancy across columns and discusses how to automatically compute and use it to substantially improve table compression.
on the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs. given a finite set v, and integers k&ge;1 and r&ge;0, let us denote by the class of hypergraphs with (k,r)-bounded intersections, i.e. in which the intersection of any k distinct hyperedges has size at most r. we consider the problem : given a hypergraph , and a subfamily of its maximal independent sets (mis) , either extend this subfamily by constructing a new mis or prove that there are no more mis, that is . it is known that, for hypergraphs of bounded dimension , as well as for hypergraphs of bounded degree (where &delta; is a constant), problem can be solved in incremental polynomial time. in this paper, we extend this result to any integers k,r such that k+r=&delta; is a constant. more precisely, we show that for hypergraphs with k+r&le;const, problem is nc-reducible to the problem of generating a single mis for a partial subhypergraph of . in particular, this implies that is polynomial, and we get an incremental polynomial algorithm for generating all mis. furthermore, combining this result with the currently known algorithms for finding a single maximally independent set of a hypergraph, we obtain efficient parallel algorithms for incrementally generating all mis for hypergraphs in the classes , , and , where &delta; is a constant. we also show that, for , where k+r&le;const, the problem of generating all mis of can be solved in incremental polynomial-time and with space polynomial only in the size of .
approximability of the capacitated b-edge dominating set problem. in this paper, we discuss the approximability of the capacitated b-edge dominating set problem, which generalizes the edge dominating set problem by introducing capacities and demands on the edges. we present an approximation algorithm for this problem and show that it achieves a factor of 8/3 for general graphs and a factor of 2 for bipartite graphs. moreover, we discuss the relationships of the edge dominating set problem and the vertex cover problem. the results show that improving the approximation factor beyond 8/3 using our approach of adding valid inequalities to a natural linear programming relaxation is as hard as improving the approximation factor for vertex cover beyond 2.
proof rules for the correctness of quantum programs. we apply the notion of quantum predicate proposed by d'hondt and panangaden to analyze a simple language fragment which may describe the quantum part of a future quantum computer in knill's architecture. the notion of weakest liberal precondition semantics, introduced by dijkstra for classical deterministic programs and by mciver and morgan for probabilistic programs, is generalized to our quantum programs. to help reasoning about the correctness of quantum programs, we extend the proof rules presented by morgan for classical probabilistic loops to quantum loops. these rules are shown to be complete in the sense that any correct assertion about the quantum loops can be proved using them. some illustrative examples are also given to demonstrate the practicality of our proof rules.
two absolute bounds for distributed bit complexity. the concept of distributed communication bit complexity was introduced by dinitz, rajsbaum, and moran. they studied the bit complexity of consensus and leader election, arriving at more or less exact bounds. this paper answers two questions on leader election, which remained there open. the first is to close the gap between the known upper and lower bounds, for electing a leader by two linked processors. the second is whether the suggested algorithm, sending 1.5n bits while electing a leader in a chain of even length n, is optimal, in the case when n is known to the processors. for both problems, absolutely exact bounds are found. moreover, the presented lower bound proofs show that there is no optimal algorithm other than the suggested ones.
traffic grooming on the path. in a wdm network, routing a request consists in assigning it a route in the physical network and a wavelength. if each request uses at most 1/c of the bandwidth of the wavelength, we will say that the grooming factor is c. that means that on a given edge of the network we can groom (group) at most c requests on the same wavelength. with this constraint the objective can be either to minimize the number of wavelengths (related to the transmission cost) or minimize the number of add drop multiplexers (shortly adm) used in the network (related to the cost of the nodes). we consider here the case where the network is a path on n nodes, pn. thus the routing is unique. for a given grooming factor c minimizing the number of wavelengths is an easy problem, well known and related to the load problem. but minimizing the number of adms is np-complete for a general set of requests and no results are known. here we show how to model the problem as a graph partition problem and using tools of design theory we completely solve the case where c=2 and where we have a static uniform all-to-all traffic (one request for each pair of vertices).
impossibility of gathering by a set of autonomous mobile robots. given a set of n autonomous mobile robots that can freely move on a two dimensional plane, they are required to gather in a position on the plane not fixed in advance (gathering problem). the main research question we address in this paper is: under which conditions can this task be accomplished by the robots? the studied robots are quite simple: they are anonymous, totally asynchronous, they do not have any memory of past computations, they cannot explicitly communicate between each other. we show that this simple task cannot be in general accomplished by the considered system of robots.
agreement in synchronous networks with ubiquitous faults. in this paper we are interested in synchronous distributed systems subject to transient and ubiquitous failures. this includes systems where failures will occur on any communication link, systems where every processor will experience at one time or another send or receive failure, etc., and, following a failure, normal functioning resuming after a finite time. notice that these cases cannot be handled by the traditional component failure models. the model we use is the communication failure model, also called the transmission failure or dynamic faults or mobile faults model. using this model, we study the fundamental problem of agreement in synchronous networks of arbitrary topology with ubiquitous faults. we establish bounds on the number of dynamic faults that make any non-trivial form of agreement (even strong majority) impossible; in turn, these bounds express connectivity requirements that must be met to achieve any meaningful form of agreement. we also provide, constructively, bounds on the number of dynamic faults in spite of which any non-trivial form of agreement (even unanimity) is possible. these bounds are shown to be tight for a large class of networks, which includes hypercubes, toruses, rings, and complete graphs; incidentally, we close the existing gap between possibility and impossibility of non-trivial agreement in complete graphs in the presence of dynamic byzantine faults. none of these results is derivable in the component failure models; in particular, all our possibility results hold in situations for which those models indicate impossibility.
hardness and approximation results for black hole search in arbitrary networks. a black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node without leaving any trace. the black hole search is the task of locating all black holes in a network by exploring it with mobile agents. we consider the problem of designing the fastest black hole search, given the map of the network and the starting node. we study the version of this problem that assumes that there is at most one black hole in the network and there are two agents, which move in synchronized steps. we prove that this problem is np-hard in arbitrary graphs (even in planar graphs), solving an open problem stated in [j. czyzowicz, d. kowalski, e. markou, a. pelc, searching for a black hole in tree networks, in: proc. 8th int. conf. on principles of distributed systems, opodis 2004, 2004, pp. 34-35. also: springer lncs, vol. 3544, pp. 67-80]. we also give a -approximation algorithm, showing the first non-trivial approximation ratio upper bound for this problem. our algorithm follows a natural approach of exploring networks via spanning trees. we prove that this approach cannot lead to an approximation ratio bound better than 3/2.
communications in unknown networks: preserving the secret of topology. in cryptography we investigate security aspects of data distributed in a network. this kind of security does not protect the secrecy of the network topology against being discovered if some kind of communication has taken place. but there are several scenarios where the network topology has to be a part of the secret. in this paper we study the question of communication within a secret network where the processing nodes of the network have only partial knowledge (e.g. given as routing tables) of the topology. we introduce a model for measuring the loss of security of the topology when far distance communication takes place. a communication protocol preserves the secret of topology if no processing node can deduce additional information about the topology from the communication. we will investigate lower bounds on the knowledge that can be revealed from the communication string and show, for instance, that some knowledge about distances can always be revealed. then, we consider routing tables. we show that several kinds of routing tables are not sufficient to guarantee the secrecy of topology. on the other hand, if a routing table allows us to specify the direction from which a message is coming, we can run a protocol solving the all-to-all communication problem such that no processing node can gain additional knowledge about the network. finally, we investigate the problem of whether routing tables can be generated from the local knowledge of the processing nodes without losing the secrecy of the network topology with respect to the resulting knowledge base. it will be shown that this is not possible for static networks and most kinds of dynamic networks.
a tight bound for online colouring of disk graphs. we present an improved upper bound on the competitiveness of the online colouring algorithm first-fit in disk graphs, which are graphs representing overlaps of disks on the plane. we also show that this bound is best possible for deterministic online colouring algorithms that do not use the disk representation of the input graph. we also present a related new lower bound for unit disk graphs.
minimization of the number of adms in sonet rings with maximum throughput with implications to the traffic grooming problem. sonet adms are dominant cost factors in wdm/sonet rings. whereas most previous papers on the topic concentrated on the number of wavelengths assigned to a given set of lightpaths, recent papers argue that the number of adms is a more realistic cost measure. the minimization of this cost factor has been investigated in recent years, where single-hop and multi-hop communication models, with arbitrary traffic and uniform traffic loads have been investigated. as a first attempt to understand the trade-off between the number of wavelengths and the number of adms, we concentrate on the all-to-all, uniform traffic instance with multi-hop, splittable communication. we look for a solution which makes full use of the bandwidth and uses the minimum possible number of adms. we develop an architecture based on successive nested polygons and present a necessary and sufficient condition for a solution in this architecture to be feasible. this architecture leads to a solution using o(wlogw+n) adms where w is the number of wavelengths used, and n is the number of nodes in the ring. this is a substantial improvement compared to nw adms for the basic architecture in [o. gerstel, p. lin, g. sasaki, combined wdm and sonet network design, in: infocom'99, eighteenth annual joint conference of the ieee computer and communications societies, vol. 2, 1999, pp. 734-743], and optimal for w=o(n/logn). we further improve this result to o(wlog$/overline{w}$+n) adms, where $/overline{w}$=o(w). this architecture constitutes a solution for the traffic grooming problem, which is the subject of many recent works.
optimal gossiping in square 2d meshes. gossiping is the communication problem in which each node has a unique message to be transmitted to every other node. the nodes exchange their message by packets. a solution to the problem is judged by how many rounds of packet sending it requires. in this paper, we consider the version of the problem in which small-size packets each carrying exactly one message are used. the nodes of the target meshes are assumed to be all-port (a node's incident edges can all be active at the same time); and their edges are either half-duplex or full-duplex, which are also known as the h* model and the f* model, respectively. we study the class of 2d square meshes. soch and tvrdik (sirocco'97, pp. 253-265; tech. rep. dc-97-04, dept. of cs&e, czech technical university) have obtained optimal algorithms for the f* model (for square or nonsquare meshes). lau and zhang (ieee trans. parallel distribut. syst. 13 (4) (2002) 349-358) have obtained fast algorithms for the h* model. we present optimal algorithms for both models, with the interesting property that they route their messages along the same paths and in the same order, i.e. for any edge {u,v}, the i-th message from u to v under either model is the same message.
on the bounded-hop mst problem on random euclidean instances. the d-dimh-hops mst problem is defined as follows: given a set s of points in the d-dimensional euclidean space and s&epsilon;s, find a minimum-cost spanning tree for s rooted at s with height at most h. we investigate the problem for any constant h and d >0. we prove the first nontrivial lower bound on the solution cost for almost all euclidean instances (i.e. the lower bound holds with high probability). then we introduce an easy-to-implement, fast divide et impera heuristic and we prove that its solution cost matches the lower bound.
languages with mismatches. in this paper we study some combinatorial properties of a class of languages that represent sets of words occurring in a text s up to some errors. more precisely, we consider sets of words that occur in a text s with k mismatches in any window of size r. the study of this class of languages mainly focuses both on a parameter, called repetition index, and on the set of the minimal forbidden words of the language of factors of s with errors. the repetition index of a string s is defined as the smallest integer such that all strings of this length occur at most in a unique position of the text s up to errors. we prove that there is a strong relation between the repetition index of s and the maximal length of the minimal forbidden words of the language of factors of s with errors. moreover, the repetition index plays an important role in the construction of an indexing data structure. more precisely, given a text s over a fixed alphabet, we build a data structure for approximate string matching having average size o(|s|log k+1|s|) and answering queries in time o(|x|+|occ(x)|) for any word x, where occ is the list of all occurrences of x in s up to errors.
on the complexity of dominating set problems related to the minimum all-ones problem. the minimum all-ones problem and the connected odd dominating set problem were shown to be np-complete in different papers for general graphs, while they are solvable in linear time (or trivial) for trees, unicyclic graphs, and series-parallel graphs. the complexity of both problems when restricted to bipartite graphs was raised as an open question. here we solve both problems. for this purpose, we introduce the related decision problem of the existence of an odd dominating set without isolated vertices, and study its complexity. our main result shows that this new problem is np-complete, even when restricted to bipartite graphs. we use this result to deduce that the minimum all-ones problem and the connected odd dominating set problem are also np-complete for bipartite graphs. we show that all three problems are solvable in linear time for graphs with bounded treewidth. we also show that the new problem remains np-complete when restricted to other graph classes, e.g., planar graphs, graphs with girth at least five, and graphs with a small maximum degree, in particular 3-regular graphs.
an exact algorithm for the minimum dominating clique problem. a subset of vertices d⊆v of a graph g=(v,e) is a dominating clique if d is a dominating set and a clique of g. the existence problem 'given a graph g, is there a dominating clique in g?' is np-complete, and thus both the minimum and the maximum dominating clique problems are np-hard. we present an o(1.3387n) time and polynomial space algorithm that for an input graph on n vertices either computes a minimum dominating clique or reports that the graph has no dominating clique. the algorithm uses the branch reduce paradigm and its time analysis is based on the measure conquer approach. we also establish a lower bound of ω(1.2599n) for the worst case running time of the algorithm. finally using memorization we obtain an o(1.3234n) time and exponential space algorithm for the same problem.
multiple genome rearrangement by swaps and by element duplications. we consider the swap distance and the element duplication distance. we show that the swap centre permutation problem is np-complete. we show that the element duplication centre problem is np-complete.
a sufficient condition for a planar graph to be class 1. we prove that every planar graph g with @d=6 is of class 1 if it does not contain a 5-cycle with a chord.
on the minimum monochromatic or multicolored subgraph partition problems. let g=(v,e) be an edge-colored graph. a subgraph h is said to be monochromatic if all the edges of h have the same color, and multicolored if no two edges of h have the same color. we investigate the complexity of the problems for finding the minimum number of monochromatic or multicolored subgraphs, such as cliques, cycles, trees and paths, partitioning v(g), depending on the number of colors used and the maximal number of times a color appears in a coloring. we also present a greedy scheme that yields a (lnm+1)-approximation for the problem of finding the minimum number of monochromatic cliques partitioning v(g) for a k"4^--free graph g, where m is the size of the largest monochromatic clique in g. by a slightly modification of the approximation algorithm, it can be used for the multicolored case. we show that unless np@?dtime(n^o^(^l^o^g^l^o^g^n^)), for any @e>=0 there is no approximation algorithm for finding the minimum number of multicolored trees partitioning v(g) with performance 50/521(1-@e)ln|v|.