Search results for "Independent set"
showing 9 items of 19 documents
Separations in Query Complexity Based on Pointer Functions
2015
In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total boolean function is given by the function $f$ on $n=2^k$ bits defined by a complete binary tree of NAND gates of depth $k$, which achieves $R_0(f) = O(D(f)^{0.7537\ldots})$. We show this is false by giving an example of a total boolean function $f$ on $n$ bits whose deterministic query complexity is $\Omega(n/\log(n))$ while its zero-error randomized query complexity is $\tilde O(\sqrt{n})$. We further show that the quantum query complexity of the same function is $\tilde O(n^{1/4})$, giving the first example of a total function with a super-quadra…
Radio Labelings of Distance Graphs
2013
A radio $k$-labeling of a connected graph $G$ is an assignment $c$ of non negative integers to the vertices of $G$ such that $$|c(x) - c(y)| \geq k+1 - d(x,y),$$ for any two vertices $x$ and $y$, $x\ne y$, where $d(x,y)$ is the distance between $x$ and $y$ in $G$. In this paper, we study radio labelings of distance graphs, i.e., graphs with the set $\Z$ of integers as vertex set and in which two distinct vertices $i, j \in \Z$ are adjacent if and only if $|i - j| \in D$.
Constructing Good Solutions for the Spanish School Timetabling Problem
1996
In the school timetabling problem a set of lessons (combinations of classes, teachers, subjects and rooms) has to be scheduled within the school week. Considering classes, teachers and rooms as resources for the lessons, the problem may be viewed as the scheduling of a project subject to resource constraints. We have developed an algorithm with three phases. In Phase I an initial solution is built by using the scheme of parallel heuristic algorithm with priority rules, but imbedding at each period the construction of a maximum cardinality independent set on a resource graph. In Phase II a tabu search procedure starts from the solution of Phase I and obtains a feasible solution to the proble…
A branch-and-cut algorithm for the pallet loading problem
2005
We propose a branch-and-cut algorithm for the pallet loading problem. The 0-1 formulation proposed by Beasley for cutting problems is adapted to the problem, adding new constraints and new procedures for variable reduction. We then take advantage of the relationship between this problem and the maximum independent set problem to use the partial linear description of its associated polyhedron. Finally, we exploit the specific structure of our problem to define the solution graph and to develop efficient separation procedures. We present computational results for the complete sets Cover I (up to 50 boxes) and Cover II (up to 100 boxes).
A Local Selection Algorithm for Switching Function Minimization
1984
The minimization algorithms which do not require any preliminary generation of all the prime implicants (PI's) of a function are the most efficient. In this work a new algorithm is described which follows such an approach. It is based on a local selection of PI's carried out by examining a set of vertices whose number is never greater than the number of PI's of a minimum cost cover. This algorithm takes advantage of a technique which uses numerical equivalents of the function vertices as pointers. For this reason it is well suited for implementation by computer. To illustrate the features of this algorithm a few examples are reported.
Incremental bipartite drawing problem
2001
Abstract Layout strategies that strive to preserve perspective from earlier drawings are called incremental. In this paper we study the incremental arc crossing minimization problem for bipartite graphs. We develop a greedy randomized adaptive search procedure (GRASP) for this problem. We have also developed a branch-and-bound algorithm in order to compute the relative gap to the optimal solution of the GRASP approach. Computational experiments are performed with 450 graph instances to first study the effect of changes in grasp search parameters and then to test the efficiency of the proposed procedure. Scope and purpose Many information systems require graphs to be drawn so that these syst…
R&D Network Formation with Myopic and Farsighted Firms
2018
We study the formation of R&D networks when each firm benefits from the research done by other firms it is connected to. Firms can be either myopic or farsighted when deciding about the links they want to form. We propose the notion of myopic-farsighted stable set to determine the R&D networks that emerge in the long run. When the majority of firms is myopic, stability leads to R&D networks consisting of either two asymmetric components with the largest component comprises three-quarters of firms or two symmetric components of nearly equal size with the largest component having only myopic firms. But, once the majority of firms becomes farsighted, only R&D networks with two asymmetric compo…
Memory-Efficient Sliding Window Progressive Meshes
2007
Progressive mesh is a data structure that encodes a continuous spectrum of mesh approximations. Sliding window progressive meshes (SWPM) minimize data transfers between CPU and GPU by storing mesh data in static on-GPU memory buffers [For01]. The main disadvantages of the original SWPM algorithm are poor vertex cache usage efficiency, and big resulting datasets. Connectivity-based algorithm [KT04] achieves a good vertex cache coherence but it does not address the problem of high memory utilization. In this paper, we describe estimates for the size of memory buffers, and describe methods to reduce the index datasets. We achieve 20% reduction due to the use hierarchical data structures (clust…
Volume preserving mean curvature flows near strictly stable sets in flat torus
2021
In this paper we establish a new stability result for the smooth volume preserving mean curvature flow in flat torus $\mathbb T^n$ in low dimensions $n=3,4$. The result says roughly that if the initial set is near to a strictly stable set in $\mathbb T^n$ in $H^3$-sense, then the corresponding flow has infinite lifetime and converges exponentially fast to a translate of the strictly stable (critical) set in $W^{2,5}$-sense.