waashk/dblp huggingface dataset:
minimal non-deletable sets and minimal non-codeletable sets in binary images. the concepts of strongly 8-deletable and strongly 4-deletable sets of 1s in binary images on the 2d cartesian grid were introduced by ronse in the mid-1980s to formalize the connectivity preservation conditions that parallel thinning algorithms are required to satisfy. in this paper we call these sets deletable and codeletable, respectively. to establish that a proposed parallel thinning algorithm for binary images on the 2d cartesian grid preserves 8-(4-)connected foreground components and 4-(8-)connected background components, it is enough to prove that the set of 1s which are changed to 0s at each pass of the algorithm is always a deletable (codeletable) set. ronse established results that are very useful in this context for proving that a finite set d of 1s is deletable or codeletable. in particular, he showed that d and its proper subsets are all codeletable in a binary image if each singleton and each pair of 8-adjacent pixels in d is codeletable. he further showed that d and its proper subsets are all deletable in a binary image if (1) each singleton and each pair of 4-adjacent pixels in d is deletable, and (2) no set of 2, 3, or 4 pairwise 8-adjacent pixels that is an 8-connected foreground component of the image is entirely contained in d. in the 1990s and early 2000s analogous results were obtained by hall, ma, gau, and the author for binary images on the 2d hexagonal grid, the 3d cartesian and face-centered cubic grids, and the 4d cartesian grid. this paper extends the above-mentioned work to binary images on almost any polytopal complex whose union is n-dimensional euclidean space, for n@?4. our main results generalize and unify the corresponding results of the earlier work.
additivity obstructions for integral matrices and pyramids. in discrete tomography there are two related notions of interest: h-uniqueness and h-additivity of finite subsets of n^m, which are defined for certain finite sets h of linear subspaces of r^m. one knows complete sets of obstructions for h-uniqueness (bad h-configurations) and for h-additivity (weakly bad h-configurations). the classical case, when h is the set of coordinate axes in r^2, is well known. let h"m denote the set of the m coordinate hyperplanes of r^m. the following question was raised in [p.c. fishburn, j.c. lagarias, j.a. reeds, l.a. shepp, sets uniquely determined by projections on axes ii. discrete case, discrete math. 91 (1991) 149-159]. is there an upper bound on the weights of the bad h"m-configurations one needs to consider to determine h"m-uniqueness (m>=3) of an arbitrary set in n^m? this question can be asked for other sets h of linear subspaces and also for h-additivity. the answer to this question, in the case of uniqueness, is known when h is a set of lines. in this paper we answer this question for uniqueness and additivity in the case of h"3. we show that there is no upper bound on the weights of the bad configurations (resp. weakly bad configurations) one needs to consider to determine h"3-uniqueness (resp. h"3-additivity).
on isoperimetrically optimal polyforms. in the plane, the way to enclose the most area with a given perimeter and to use the shortest perimeter to enclose a given area, is always to use a circle. if we replace the plane by a regular tiling of it, and construct polyforms i.e. shapes as sets of tiles, things become more complicated. we need to redefine the area and perimeter measures, and study the consequences carefully. a spiral construction often provides, for every integer number of tiles (area), a shape that is most compact in terms of the perimeter or boundary measure; however it may not exhibit all optimal shapes. we characterize in this paper all shapes that have both shortest boundaries and maximal areas for three common planar discrete spaces.
a framework for generating some discrete sets with disjoint components by using uniform distributions. discrete tomography deals with the reconstruction of discrete sets from few projections. assuming that the set to be reconstructed belongs to a certain class of discrete sets with some geometrical properties is a commonly used technique to reduce the number of possibly many different solutions of the same reconstruction problem. the average performance of reconstruction algorithms are often tested on such classes by choosing elements of a given class from uniform random distributions. this paper presents a general framework for generating discrete sets with disjoint connected components using uniform distributions. especially, the uniform random generation of hv-convex discrete sets and q-convex discrete sets according to the size of the minimal bounding rectangle are discussed.
a finite set of functions with an exptime-complete composition problem. we exhibit a finite family of functions over a finite set (i.e. a finite algebra), such that the problem whether a given function can be obtained as a composition of the members of this family (i.e. is a member of the clone generated by the algebra) is exptime-complete.
time separations of cyclic event rule systems with min-max timing constraints. the analysis of the time separations of events is a fundamental problem in the design and evaluation of discrete event systems. important progresses have been made based on the event rule system model in the last decade. the existing results for event rule systems with min and max constraints can be summarized briefly as: the exact evaluation of time separations for acyclic systems is np-complete; for cyclic systems, the structural condition of being tightly coupled is sufficient for long-term time separations of events to be bounded. in this paper, we establish a necessary and sufficient structural boundedness condition-uniformity for cyclic event rule systems with both min and max constraints. tightly coupled systems are shown to be a special class of uniform systems. the well-known cas algorithm for finding bounds on long-term time separations is adapted to find finite bounds for uniform systems. our results are obtained by exploring the algebraic structures guiding the evolution of the systems.
subword histories and associated matrices. the basic numerical quantity investigated in this paper is |w|"u, the number of occurrences of a word u as a scattered subword of a word w. arithmetical combinations of such quantities yield a so-called subword history. we investigate the information content of subword histories. reducing subword histories to linear ones, as well as the recently introduced parikh matrices, will be important tools. simple polynomial formulas for computing the value of a subword history for arbitrary powers of a word are obtained.
on the bandwidth of 3-dimensional hamming graphs. this paper presents strategies for improving the known upper and lower bounds for the bandwidth of hamming graphs (k"n)^d and [0,1]^d. our labeling strategy lowers the upper bound on the bandwidth of the continuous hamming graph, [0,1]^3, from .5 to .4497. a lower bound of .4439 on bw([0,1]^3) follows from known isoperimetric inequalities and a related dynamic program is conjectured to raise that lower bound to 4/9=.4444.... in particular, showing the power of our method, we prove that the bandwidth of k"6xk"6xk"6 is exactly 101.
main-memory triangle computations for very large (sparse (power-law)) graphs. finding, counting and/or listing triangles (three vertices with three edges) in massive graphs are natural fundamental problems, which have recently received much attention because of their importance in complex network analysis. here we provide a detailed survey of proposed main-memory solutions to these problems, in a unified way. we note that previous authors have paid surprisingly little attention to space complexity of main-memory solutions, despite its both fundamental and practical interest. we therefore detail space complexities of known algorithms and discuss their implications. we also present new algorithms which are time optimal for triangle listing and beats previous algorithms concerning space needs. they have the additional advantage of performing better on power-law graphs, which we also detail. we finally show with an experimental study that these two algorithms perform very well in practice, allowing us to handle cases which were previously out of reach.
parallel time and space upper-bounds for the subset-sum problem. three new parallel scalable algorithms for solving the subset-sum problem in o(np(c-w"m"i"n)) time and o(n+c) space in the pram model are presented, where n is the number of objects, c is the capacity, w"m"i"n is the smallest weight and p is the number of processors. these time and space bounds are better than the direct parallelization of bellman's algorithm, which was the most efficient known result.
lower bounds and new constructions on secure group communication schemes. this paper presents both the theoretical and practical aspects of secure group communication schemes. we pointed out that multiple revocation is a fundamentally time-consuming task in secure group communication, by establishing lower bounds for broadcast encryption and group key distribution schemes. we showed that they are o(n) for be and o(n/m) for gkd respectively, where m is storage requirement and n is the number of users. thus, they are clearly far more costly than the ideal log bound. in practice, we designed a new broadcast encryption scheme rbe that actually achieves these lower bounds. rbe is shown to outperform most efficient be schemes in mass revocation. we discuss the influence of join as well as the feasibility of adding it in be schemes by means of performing full updating or overprovisioning.
on complexity functions of infinite words associated with generalized dyck languages. in this article, we construct a family of infinite words, generated by countable automata and also generated by substitutions over infinite alphabets, closely related to parenthesis languages and we study their complexity functions. we obtain a family of binary infinite words m^(^b^), indexed on the number b>=1 of parenthesis types, such that the growth order of the complexity function of m^(^b^) is n(logn)^2 if b=1 and n^1^+^l^o^g^"^2^"^b^b if b>=2.
exponential lower bounds on the size of constant-depth threshold circuits with small energy complexity. a complexity measure for threshold circuits, called the energy complexity, has been proposed to measure an amount of energy consumed during computation in the brain. biological neurons need more energy to transmit a ''spike'' than not to transmit one, and hence the energy complexity of a threshold circuit is defined as the number of gates in the circuit that output ''1'' during computation. since the firing activity of neurons in the brain is quite sparse, the following question arises: what boolean functions can or cannot be computed by threshold circuits with small energy complexity. in the paper, we partially answer the question, that is, we show that there exists a trade-off among three complexity measures of threshold circuits: the energy complexity, size, and depth. the trade-off implies an exponential lower bound on the size of constant-depth threshold circuits with small energy complexity for a large class of boolean functions.
universal automata and nfa learning. the aim of this paper is to develop a new algorithm that, with a complete sample as input, identifies the family of regular languages by means of nondeterministic finite automata. it is a state-merging algorithm. one of its main features is that the convergence (which is proved) is achieved independently from the order in which the states are merged, that is, the merging of states may be done ''randomly''.
tiling problems, automata, and tiling graphs. this paper continues the investigation of tiling problems via formal languages, which was begun in papers by merlini, sprugnoli, and verri. those authors showed that certain tiling problems could be encoded by regular languages, which lead automatically to generating functions and other combinatorial information on tilings. we introduce a method of simplifying the dfa's recognizing these language, which leads to bijective proofs of certain tiling identities. we apply these ideas to some other tiling problems, including three-dimensional tilings and tilings with triangles and rhombi. we also study graph-theoretic variations of these tiling problems.
game chromatic index of graphs with given restrictions on degrees. given a graph g and an integer k, two players alternatively color the edges of g using k colors so that adjacent edges get different colors. the game chromatic index@g"g^'(g) is the minimum k for which the first player has a strategy that ensures that all edges of g get colored. the trivial bounds are @d(g)@?@g"g^'(g)@?2@d(g)-1, where @d(g) denotes the maximal degree of g. lam, shiu, and xu and, independently, bartnicki and grytczuk asked whether there is a constant c such that @g"g^'(g)@?@d(g)+c for every graph g. we show that the answer is in the negative by constructing graphs g such that @g"g^'(g)>=1.008@d(g) and @d(g)->~. on the other hand, we show that for every @m>0 there is @e>0 such that for any graph g with @d(g)>=(1/2+@m)v(g), we have @g"g^'(g)@?(2-@e)@d(g), where v(g) denotes the number of vertices of g.
equitable list colorings of planar graphs without short cycles. a graph g is equitably k-choosable if, for any k-uniform list assignment l, g is l-colorable and each color appears on at most @?|v(g)|k@? vertices. a graph g is equitably k-colorable if g has a proper k-vertex coloring such that the sizes of any two color classes differ by at most 1. in this paper, we prove that every planar graph g is equitably k-choosable and equitably k-colorable if one of the following conditions holds: (1) g is triangle-free and k>=max{@d(g),8}; (2) g has no 4- and 5-cycles and k>=max{@d(g),7}.
fault-tolerant embedding of paths in crossed cubes. the crossed cube cq"n is an important variant of the hypercube q"n and possesses many desirable properties for interconnection networks. this paper shows that in cq"n with f"v faulty vertices and f"e faulty edges there exists a fault-free path of length @? between any two distinct fault-free vertices for each @? satisfying 2^n^-^1-1@?@?@?2^n-f"v-1 provided that f"v+f"e@?n-3, where the lower bound of @? and the upper bound of f"v+f"e are tight for some n. moreover, this result improves the known result that cq"n is (n-3)-hamiltonian connected.
testing whether a digraph contains h-free k-induced subgraphs. a subgraph induced by k vertices is called a k-induced subgraph. we prove that determining if a digraph g contains h-free k-induced subgraphs is @w(n^2)-evasive. then we construct an @e-tester to test this property. (an @e-tester for a property @p is guaranteed to distinguish, with probability at least 2/3, between the case of g satisfying @p and the case of g being @e-far from satisfying @p.) the query complexity of the @e-tester is independent of the size of the input digraph. an (@e,@d)-tester for a property @p is an @e-tester for @p that is furthermore guaranteed to accept with probability at least 2/3 any input that is @d-close to satisfying @p. this paper presents an (@e,@d)-tester for whether a digraph contains h-free k-induced subgraphs.
arbitrary pattern formation by asynchronous, anonymous, oblivious robots. from an engineering point of view, the problem of coordinating a set of autonomous, mobile robots for the purpose of cooperatively performing a task has been studied extensively over the past decade. in contrast, in this paper we aim to understand the fundamental algorithmic limitations on what a set of autonomous mobile robots can or cannot achieve. we therefore study a hard task for a set of weak robots. the task is for the robots in the plane to form any arbitrary pattern that is given in advance. this task is fundamental in the sense that if the robots can form any pattern, they can agree on their respective roles in a subsequent, coordinated action. the robots are weak in several aspects. they are anonymous; they cannot explicitly communicate with each other, but only observe the positions of the others; they cannot remember the past; they operate in a very strong form of asynchronicity. we show that the tasks that such a system of robots can perform depend strongly on their common agreement about their environment, i.e. the readings of their environment sensors. if the robots have no common agreement about their environment, they cannot form an arbitrary pattern. if each robot has a compass needle that indicates north (the robot world is a flat surface, and compass needles are parallel), then any odd number of robots can form an arbitrary pattern, but an even number cannot (in the worst case). if each robot has two independent compass needles, say north and east, then any set of robots can form any pattern.
a dynamic data structure for top-k queries on uncertain data. in an uncertain data sets=(s,p,f) where s is the ground set consisting of n elements, p:s->[0,1] a probability function, and f:s->r a score function, each element i@?s with score f(i) appears independently with probability p(i). the top-k query on s asks for the set of k elements that has the maximum probability of appearing to be the k elements with the highest scores in a random instance of s. computing the top-k answer on a fixed s is known to be easy. in this paper, we consider the dynamic problem, that is, how to maintain the top-k query answer when s changes, including element insertions and deletions in the ground set s, changes in the probability function p and in the score function f. we present a fully dynamic data structure that handles an update in o(klogn) time, and answers a top-j query in o(logn+j) time for any j@?k. the structure has o(n) size and can be constructed in o(nlogk) time. as a building block of our dynamic structure, we present an algorithm for the all-top-k problem, that is, computing the top-j answers for all j=1,...,k, which may be of independent interest.
computational complexity of quantified boolean formulas with fixed maximal deficiency. the paper investigates the computational complexity of quantified boolean formulas with fixed maximal deficiency. the satisfiability problem for quantified boolean formulas with maximal deficiency 1 is shown to be solvable in polynomial time. for k>=1, it is shown that true formulas with fixed maximal deficiency k have models in which all boolean functions can be represented as cnf formulas over at most 2^4^k^/^3 universal variables. as a consequence, the satisfiability problem for qcnf formulas with fixed maximal deficiency is in np and for fixed deficiency the minimal falsity problem is in d^p. for two subclasses of quantified boolean formulas with pspace-complete evaluation problem, qehorn and qe2-cnf , we show that for fixed deficiency the minimal falsity problem can be decided in polynomial time.
on varieties of meet automata. eilenberg's variety theorem gives a bijective correspondence between varieties of languages and varieties of finite monoids. the second author gave a similar relation between conjunctive varieties of languages and varieties of semiring homomorphisms. in this paper, we add a third component to this result by considering varieties of meet automata. we consider three significant classes of languages, two of them consisting of reversible languages. we present conditions on meet automata and identities for semiring homomorphisms for their characterization.
dense open-shop schedules with release times. we study open-shop scheduling problems with job release times. the objective is to minimize the makespan. dense schedules, easy to construct, are often used as approximate solutions. performance ratios of the makespans from dense schedules and that of the optimal schedule of the problem are used to evaluate the quality of approximate schedules. it is conjectured (proved for a limited number of machines) that this performance ratio is bounded above by (2-1/m) for m-machine open-shop problems without job release times. in this paper, we extend the conjecture to open-shop problems with job release times. the results proved in this paper are: 1. dense schedule performance ratio is bounded above by 2 for three-machine open-shop problems with job release times; 2. the conjectured performance ratio upper bound of 5/3 is proved for two special cases of three-machine open-shop problems with job release times; 3. a performance ratio upper bound of 7/4 is proved for three-machine problems.
monotonicity in digraph search problems. in this paper, we study the monotonicity and complexity of five digraph search problems: directed searching, mixed directed searching, internal directed searching, internal strong searching, and internal weak searching. in the first three search problems, both searchers and intruder must follow the edge directions when they move along edges. in the internal strong search problem, the intruder must move in the edge directions but searchers need not. in the internal weak search problem, searchers must move in the edge directions but the intruder need not. there are three actions for searchers in the first two search problems: placing, removing and sliding, and there are only two actions for searchers in the last three internal search problems: placing and sliding. note that the internal strong searching is a ''strong'' version of the internal directed searching, the internal weak searching is a ''weak'' version of the internal directed searching, and the internal edge searching is an analogy of the internal directed searching on undirected graphs. we prove that the first three problems are monotonic and the last two problems are non-monotonic, respectively. it is interesting that the internal directed searching is monotonic while the internal strong searching, the internal weak searching and the internal edge searching are all non-monotonic. we also show that the first four problems are np-complete and the last problem is np-hard. we solve the open problem on whether a non-monotonic searching problem can be np-complete.
the 2-radius and 2-radiian problems on trees. in this paper, we consider two facility location problems on tree networks. one is the 2-radius problem, whose goal is to partition the vertex set of the given network into two non-empty subsets such that the sum of the radii of these two induced subgraphs is minimum. the other is the 2-radiian problem, whose goal is to partition the network into two non-empty subsets such that the sum of the centdian values of these two induced subgraphs is minimum. we propose an o(n)-time algorithm for the 2-radius problem on trees and an o(nlogn)-time algorithm for the 2-radiian problem on trees, where n is the number of vertices in the given tree.
solving structured linear systems with large displacement rank. linear systems with structures such as toeplitz, vandermonde or cauchy-likeness can be solved in o@?(@a^2n) operations, where n is the matrix size, @a is its displacement rank, and o@? denotes the omission of logarithmic factors. we show that for such matrices, this cost can be reduced to o@?(@a^@w^-^1n), where @w is a feasible exponent for matrix multiplication over the base field. the best known estimate for @w is @w
online unit clustering: variations on a theme. online unit clustering is a clustering problem where classification of points is done in an online fashion, but the exact location of clusters can be modified dynamically. we study several variants and generalizations of the online unit clustering problem, which are inspired by variants of packing and scheduling problems in the literature.
fault-free hamiltonian cycles in twisted cubes with conditional link faults. the n-dimensional twisted cube, denoted by tq"n, a variation of the hypercube, possesses some properties superior to the hypercube. in this paper, assuming that each vertex is incident with at least two fault-free links, we show that tq"n can tolerate up to 2n-5 edge faults, while retaining a fault-free hamiltonian cycle. the result is optimal with respect to the number of edge faults tolerated.