Journal articles: 'Hypercuts'

1

Linial, Nati, Ilan Newman, Yuval Peled, and Yuri Rabinovich. "Extremal hypercuts and shadows of simplicial complexes." Israel Journal of Mathematics 229, no. 1 (2019): 133–63. http://dx.doi.org/10.1007/s11856-018-1803-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Nikutta, Robert, Enrique Lopez-Rodriguez, Kohei Ichikawa, Nancy A. Levenson, and Christopher C. Packham. "Hypercat - hypercube of AGN tori." Proceedings of the International Astronomical Union 15, S356 (2019): 44–49. http://dx.doi.org/10.1017/s1743921320002550.

Full text

Abstract:

AbstarctWe introduce Hypercat, a large set of 2-d AGN torus images computed with the state-of-the-art clumpy radiative transfer code Clumpy. The images are provided as a 9-dimensional hypercube, in addition to a smaller hypercube of corresponding projected dust distribution maps. Hypercat also comprises a software suite for easy use of the hypercubes, quantification of image morphology, and simulation of synthetic observations with single-dish telescopes, interferometers, and Integral Field Units. We apply Hypercat to NGC 1068 and find that it can be spatially resolved in Near- and Mid-IR, for the first time with single-dish apertures, on the upcoming generation of 25–40m class telescopes. We also find that clumpy AGN torus models within a range of the parameter space can explain on scales of several parsec the recently reported polar elongation of MIR emission in several sources, while not upending basic assumptions about AGN unification.

APA, Harvard, Vancouver, ISO, and other styles

3

Wee, Jaehyung, Jin-Ghoo Choi, and Wooguil Pak. "Wildcard Fields-Based Partitioning for Fast and Scalable Packet Classification in Vehicle-to-Everything." Sensors 19, no. 11 (2019): 2563. http://dx.doi.org/10.3390/s19112563.

Full text

Abstract:

Vehicle-to-Everything (V2X) requires high-speed communication and high-level security. However, as the number of connected devices increases exponentially, communication networks are suffering from huge traffic and various security issues. It is well known that performance and security of network equipment significantly depends on the packet classification algorithm because it is one of the most fundamental packet processing functions. Thus, the algorithm should run fast even with the huge set of packet processing rules. Unfortunately, previous packet classification algorithms have focused on the processing speed only, failing to be scalable with the rule-set size. In this paper, we propose a new packet classification approach balancing classification speed and scalability. It can be applied to most decision tree-based packet classification algorithms such as HyperCuts and EffiCuts. It determines partitioning fields considering the rule duplication explicitly, which makes the algorithm memory-effective. In addition, the proposed approach reduces the decision tree size substantially with the minimal sacrifice of classification performance. As a result, we can attain high-speed packet classification and scalability simultaneously, which is very essential for latest services such as V2X and Internet-of-Things (IoT).

APA, Harvard, Vancouver, ISO, and other styles

4

Röttger, Markus, and Ulf-Peter Schroeder. "Embedding 2-Dimensional Grids Into Optimal Hypercubes with Edge-Congestion 1 or 2." Parallel Processing Letters 08, no. 02 (1998): 231–42. http://dx.doi.org/10.1142/s0129626498000249.

Full text

Abstract:

This paper explores one-to-one embeddings of 2-dimensional grids into hypercubes. It is shown that each 2-dimensional grid can be embedded with edge-congestion 2 into its optimal hypercube (the smallest hypercube with at least as many nodes as the grid). Additionally, a technique is developed to embed many 2-dimensional grids into their optimal hypercubes with edge-congestion 1.

APA, Harvard, Vancouver, ISO, and other styles

5

Prabhu, Savari, Arumugam Krishnan Arulmozhi, and M. Arulperumjothi. "Certain Domination Parameters and Their Resolving Versions of Fractal Cubic Networks." Fractal and Fractional 8, no. 12 (2024): 747. https://doi.org/10.3390/fractalfract8120747.

Full text

Abstract:

Networks are designed to communicate, operate, and allocate tasks to respective commodities. Operating supercomputers became challenging, which was handled by the network design commonly known as hypercube, denoted by Qn. In a recent study, the hypercube networks were insufficient to hold supercomputers’ parallel processors. Thus, variants of hypercubes were discovered to produce an alternative to the hypercube. A new variant of the hypercube, the fractal cubic network, can be used as the best alternative in the case of hypercubes. Our research investigates that the fractal cubic network is a rooted product of two graphs. We try to determine its domination and resolving domination parameters, which could be applied to resource location and broadcasting-related problems.

APA, Harvard, Vancouver, ISO, and other styles

6

Burkov, Andriy, and Brahim Chaib-draa. "An Approximate Subgame-Perfect Equilibrium Computation Technique for Repeated Games." Proceedings of the AAAI Conference on Artificial Intelligence 24, no. 1 (2010): 729–36. http://dx.doi.org/10.1609/aaai.v24i1.7623.

Full text

Abstract:

This paper presents a technique for approximating, up to any precision, the set of subgame-perfect equilibria (SPE) in repeated games with discounting. The process starts with a single hypercube approximation of the set of SPE payoff profiles. Then the initial hypercube is gradually partitioned on to a set of smaller adjacent hypercubes, while those hypercubes that cannot contain any SPE point are gradually withdrawn. Whether a given hypercube can contain an equilibrium point is verified by an appropriate mixed integer program. A special attention is paid to the question of extracting players' strategies and their representability in form of finite automata.

APA, Harvard, Vancouver, ISO, and other styles

7

HUANG, KE, and JIE WU. "AREA EFFICIENT LAYOUT OF BALANCED HYPERCUBES." International Journal of High Speed Electronics and Systems 06, no. 04 (1995): 631–45. http://dx.doi.org/10.1142/s0129156495000237.

Full text

Abstract:

As a multicomputer structure, the balanced hypercube is a variant of the standard hypercube for multicomputers, with desirable properties of strong connectivity, regularity, and symmetry. This structure is a special type of load balanced graph designed to tolerate processor failure. In balanced hypercubes, each processor has a backup (matching) processor that shares the same set of neighboring nodes. Therefore, tasks that run on a faulty processor can be reactivated in the backup processor to provide efficient system reconfiguration. In this paper, we study the implementation of balanced hypercubes in VLSI using the Wafer Scale Integration (VLSI/WSI) technology. Emphasis is on VLSI/WSI layout and area estimates. Our results show that the balanced hypercube can be implemented at least as efficient as the standard hypercube in an area layout and more efficient in a linear layout.

APA, Harvard, Vancouver, ISO, and other styles

8

Kim, Jin S., Seung Ryoul Maeng, and H. Yoon. "Ring Embedding in Hypercubes with Faculty Nodes." Parallel Processing Letters 07, no. 03 (1997): 285–96. http://dx.doi.org/10.1142/s0129626497000309.

Full text

Abstract:

Hypercube is an attractive structure for parellel processing due to its symmetry and regularity. To increase the reliability of hypercube based systems and to allow their use in the presence of faulty nodes, efficient fault-tolerant schemes in hypercubes are necessary. In this paper, we present an algorithm for embedding rings in hypercubes based multiprocessor network in the event of node failures. The algorithm can tolerate up to θ(2n/2) faults, and guarantee that given any f < (n - 2k)2k faulty nodes, it can find a ring of size at least 2n - 2f for k = 0 and 2n - 2k f - 22k for k ≥ 1 in an n-dimensional hypercube. It improves over existing algorithms in the size of ring.

APA, Harvard, Vancouver, ISO, and other styles

9

Liu, Jia-Bao, Xiang-Feng Pan, and Jinde Cao. "Some Properties on Estrada Index of Folded Hypercubes Networks." Abstract and Applied Analysis 2014 (2014): 1–6. http://dx.doi.org/10.1155/2014/167623.

Full text

Abstract:

LetGbe a simple graph withnvertices and letλ1,λ2,…,λnbe the eigenvalues of its adjacency matrix; the Estrada indexEEGof the graphGis defined as the sum of the termseλi, i=1,2,…,n. Then-dimensional folded hypercube networksFQnare an important and attractive variant of then-dimensional hypercube networksQn, which are obtained fromQnby adding an edge between any pair of vertices complementary edges. In this paper, we establish the explicit formulae for calculating the Estrada index of the folded hypercubes networksFQnby deducing the characteristic polynomial of the adjacency matrix in spectral graph theory. Moreover, some lower and upper bounds for the Estrada index of the folded hypercubes networksFQnare proposed.

APA, Harvard, Vancouver, ISO, and other styles

10

WU, JIE. "TIGHT BOUNDS ON THE NUMBER OF l-NODES IN A FAULTY HYPERCUBE." Parallel Processing Letters 05, no. 02 (1995): 321–28. http://dx.doi.org/10.1142/s0129626495000308.

Full text

Abstract:

The spanning binomial tree is one of most frequently used spanning tree structures to implement various parallel applications in multiprocessor systems, such as hypercubes. In this paper, we define an l-node as a root node of an incomplete spanning binomial tree of a hypercube, which is defined as a connected subtree of a spanning binomial tree with the same root node that connects all the nonfaulty nodes in the hypercube. We show that in an n-dimensional hypercube with m faulty nodes there are at least 2n − 2ml-nodes. This implies that at least half of the nodes of the hypercube are l-nodes if the number of faulty nodes is less than the dimension of the hypercube.

APA, Harvard, Vancouver, ISO, and other styles

11

ZIAVRAS, SOTIRIOS G. "SCALABLE MULTIFOLDED HYPERCUBES FOR VERSATILE PARALLEL COMPUTERS." Parallel Processing Letters 05, no. 02 (1995): 241–50. http://dx.doi.org/10.1142/s0129626495000229.

Full text

Abstract:

This paper introduces the family of scalable multifolded hypercube (SMH) architectures for parallel computers. Scalability and versatility at resonable cost are the major characteristics of these architectures. SMHs perform comparable to generalized hypercubes for important classes of algorithms that use regular communication patterns. In addition, they often achieve better performance than the popular direct binary hypercubes because they can emulate efficiently a powerful family of multifolded direct binary hypercubes. Extensive comparison of cost with binary and generalized hypercubes is also included. The hardware cost of SMH's is shown to be even lower than that of fat trees. Therefore, SMH's are viable candidates for the construction of versatile parallel computers.

APA, Harvard, Vancouver, ISO, and other styles

12

BEST, ANA, MARKUS KLIEGL, SHAWN MEAD-GLUCHACKI, and CHRISTINO TAMON. "MIXING OF QUANTUM WALKS ON GENERALIZED HYPERCUBES." International Journal of Quantum Information 06, no. 06 (2008): 1135–48. http://dx.doi.org/10.1142/s0219749908004377.

Full text

Abstract:

We study continuous-time quantum walks on graphs which generalize the hypercube. The only known family of graphs whose quantum walk instantaneously mixes to uniform is the Hamming graphs with small arities. We show that quantum uniform mixing on the hypercube is robust under the addition of perfect matchings but not much else. Our specific results include: • The graph obtained by augmenting the hypercube with an additive matching x ↦ x ⊕ η is instantaneous uniform mixing whenever |η| is even, but with a slower mixing time. This strictly includes the result of Moore and Russell1 on the hypercube. • The class of Hamming graphs H(n,q) is not uniform mixing if and only if q ≥ 5. This is a tight characterization of quantum uniform mixing on Hamming graphs; previously, only the status of H(n,q) with q < 5 was known. • The bunkbed graph [Formula: see text] whose adjacency matrix is I ⊗ Qn + X ⊗ Af, where Af is a [Formula: see text]-circulant matrix defined by a Boolean function f, is not uniform mixing if the Fourier transform of f has support of size smaller than 2n-1. This explains why the hypercube is uniform mixing and why the join of two hypercubes is not. Our work exploits the rich spectral structure of the generalized hypercubes and relies heavily on Fourier analysis of group-circulants.

APA, Harvard, Vancouver, ISO, and other styles

13

Kumar, J. M., and L. M. Patnaik. "Extended hypercube: a hierarchical interconnection network of hypercubes." IEEE Transactions on Parallel and Distributed Systems 3, no. 1 (1992): 45–57. http://dx.doi.org/10.1109/71.113081.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

José, Marco V., Eberto R. Morgado, and Juan R. Bobadilla. "Groups of Symmetries of the Two Classes of Synthetases in the Four-Dimensional Hypercubes of the Extended Code Type II." Life 13, no. 10 (2023): 2002. http://dx.doi.org/10.3390/life13102002.

Full text

Abstract:

Aminoacyl-tRNA synthetases (aaRSs) originated from an ancestral bidirectional gene (mirror symmetry), and through the evolution of the genetic code, the twenty aaRSs exhibit a symmetrical distribution in a 6-dimensional hypercube of the Standard Genetic Code. In this work, we assume a primeval RNY code and the Extended Genetic RNA code type II, which includes codons of the types YNY, YNR, and RNR. Each of the four subsets of codons can be represented in a 4-dimensional hypercube. Altogether, these 4 subcodes constitute the 6-dimensional representation of the SGC. We identify the aaRSs symmetry groups in each of these hypercubes. We show that each of the four hypercubes contains the following sets of symmetries for the two known Classes of synthetases: RNY: dihedral group of order 4; YNY: binary group; YNR: amplified octahedral group; and RNR: binary group. We demonstrate that for each hypercube, the group of symmetries in Class 1 is the same as the group of symmetries in Class 2. The biological implications of these findings are discussed.

APA, Harvard, Vancouver, ISO, and other styles

15

Lobov, Alexander A., and Mikhail B. Abrosimov. "About uniqueness of the minimal 1-edge extension of hypercube Q4." Prikladnaya Diskretnaya Matematika, no. 58 (2023): 84–93. http://dx.doi.org/10.17223/20710410/58/8.

Full text

Abstract:

One of the important properties of reliable computing systems is their fault tolerance. To study fault tolerance, you can use the apparatus of graph theory. Minimal edge extensions of a graph are considered, which are a model for studying the failure of links in a computing system. A graph G* = (V*,α*) with n vertices is called a minimal k-edge extension of an n-vertex graph G = (V, α) if the graph G is embedded in every graph obtained from G* by deleting any of its k edges and has the minimum possible number of edges. The hypercube Qn is a regular 2n-vertex graph of order n, which is the Cartesian product of n complete 2-vertex graphs K2. The hypercube is a common topology for building computing systems. Previously, a family of graphs Q*n was described, whose representatives for n>1 are minimal edge 1-extensions of the corresponding hypercubes. In this paper, we obtain an analytical proof of the uniqueness of minimal edge 1-extensions of hypercubes for n≤4 and establish a general property of an arbitrary minimal edge 1-extension of a hypercube Qn for n>2: it does not contain edges connecting vertices, the distance between which in the hypercube is equal to 2.

APA, Harvard, Vancouver, ISO, and other styles

16

Chang, Hsuan-Han, Kuan-Ting Chen, and Pao-Lien Lai. "How to Systematically Embed Cycles in Balanced Hypercubes." International Journal of Software Innovation 5, no. 1 (2017): 44–56. http://dx.doi.org/10.4018/ijsi.2017010104.

Full text

Abstract:

The balanced hypercube is a variant of the hypercube structure and has desirable properties like connectivity, regularity, and symmetry. The cycle is a popular interconnection topology and has been widely used in distributed-memory parallel computers. Moreover, parallel algorithms of cycles have been extensively developed and used. The problem of how to embed cycles into a host graph has attracted a great attention in recent years. However, there is no systematic method proposed to generate the desired cycles in balanced hypercubes. In this paper, the authors develop systematic linear time algorithm to construct cycles and Hamiltonian cycles for the balanced hypercube.

APA, Harvard, Vancouver, ISO, and other styles

17

Santoso, Eko Budi, Reginaldo M. Marcelo, and Mari-Jo P. Ruiz. "On Independent [1, 2]-sets in Hypercubes." ITM Web of Conferences 71 (2025): 01017. https://doi.org/10.1051/itmconf/20257101017.

Full text

Abstract:

Given a simple graph G, a subset S ⊆ V(G) is an independent [1, 2]-set if no two vertices in S are adjacent and for every vertex υ ϵ V(G)\S, 1 ≤ |N(υ) ∩ S | ≤ 2, that is, every vertex υ ϵ V(G)\S is adjacent to at least one but not more than two vertices in S. This paper investigates the existence of independent [1, 2]-sets of hypercubes. We show that for some positive integer k, if n = 2k − 1, then hypercubes Qn and Qn+1 have an independent [1, 2]-set. Furthermore, for 1 ≤ n ≤ 4, we find bounds for the minimum and maximum cardinality of an independent [1, 2]-set of hypercube Qn, while for n = 5, 6, we get the maximum of cardinality of an independent [1, 2]-set of hypercube Qn.

APA, Harvard, Vancouver, ISO, and other styles

18

LATIFI, SHAHRAM. "SUBCUBE EMBEDDABILITY OF FOLDED HYPERCUBES." Parallel Processing Letters 01, no. 01 (1991): 43–50. http://dx.doi.org/10.1142/s0129626491000203.

Full text

Abstract:

The Folded Hypercube (FHC) has been proven to be an attractive hypercube-based network. This paper closely compares the FHC to its standard hypercube counterpart from the subcube allocation viewpoint. It is shown that the FHC(n) outperforms the n-dimensional hypercube (n-cube for short) in offering subcubes of size k by a factor of [Formula: see text]. In an environment where subcubes of the original network must be allocated to incoming tasks, the FHC achieves an excellent processor utilization by assigning subcubes in an efficient and compact manner. Using the concept of virtual hypercubes, an efficient way is suggested to recognize the available subcubes in the FHC by adapting the already developed subcube recognition algorithms. An alternative approach to the subcube recognition problem is also given.

APA, Harvard, Vancouver, ISO, and other styles

19

XIANG, DONG, AI CHEN, and JIE WU. "LOCAL-SAFETY-INFORMATION-BASED BROADCASTING IN HYPERCUBE MULTICOMPUTERS WITH NODE AND LINK FAULTS." Journal of Interconnection Networks 02, no. 03 (2001): 365–78. http://dx.doi.org/10.1142/s0219265901000440.

Full text

Abstract:

This paper presents a method to cope with fault-tolerant broadcasting in hypercube multicomputers with both node and link faults. The local safety concept is extended to faulty hypercubes with both node and link faults. The local-safety-based algorithm is used in a fully unsafe hypercube, where there is no safe node. A fully unsafe hypercube can be split into a set of maximal safe subcubes. We show that if these maximal safe subcubes meet certain requirements given in the paper, broadcasting can still be carried out successfully and in some case optimal broadcast is still possible. The method is extended to fault-tolerant routing and multicasting when the system contains both node and link faults.

APA, Harvard, Vancouver, ISO, and other styles

20

HSU, GUO-HUANG, CHIEH-FENG CHIANG, and JIMMY J. M. TAN. "COMPARISON-BASED CONDITIONAL DIAGNOSABILITY ON THE CLASS OF HYPERCUBE-LIKE NETWORKS." Journal of Interconnection Networks 11, no. 03n04 (2010): 143–56. http://dx.doi.org/10.1142/s0219265910002775.

Full text

Abstract:

For system diagnosis, Lai et al.16 introduced a new measurement, called the conditional diagnosability, by adding a condition that no faulty set contains all the neighbors of any vertex in a network. Taking the hypercube as the target, Lai et al.16 (respectively, Hsu et al.13) estimated the PMC-based19 (respectively, the comparison-based18) conditional diagnosability as about four (respectively, three) times larger than the original diagnosability. In this paper, we extend the concept of conditional diagnosability to the generalized version of hypercubes, the class of hypercube-like networks. We prove that the conditional diagnosability of an n-dimensional hypercube-like network HLn is 3n - 5 under the comparison diagnosis model, for n ≥ 5.

APA, Harvard, Vancouver, ISO, and other styles

21

Zelina, Ioana, Mara Hajdu-Măcelaru, and Cristina Ţicală. "About the cube polynomial of Extended Fibonacci Cubes." Creative Mathematics and Informatics 27, no. 1 (2018): 95–100. http://dx.doi.org/10.37193/cmi.2018.01.13.

Full text

Abstract:

The hypercube is one of the best model for the network topology of a distributed system. In this paper we determine the cube polynomial of Extended Fibonacci Cubes, which is the counting polynomial for the number of induced k-dimensional hypercubes in Extended Fibonacci Cubes.

APA, Harvard, Vancouver, ISO, and other styles

22

Fakharan, Mohammadhossein, Hovhannes A. Harutyunyan, and Pouria Alikhanifard. "Broadcast Schemes of Hypercubes." Journal of Graph Algorithms and Applications 29, no. 1 (2025): 125–34. https://doi.org/10.7155/jgaa.v29i1.3011.

Full text

Abstract:

Broadcasting is a fundamental process in network communication, modeled as the dissemination of information across vertices in a graph. This paper investigates the broadcast problem in hypercube graphs and revisits the dimensional broadcast schemes. We propose a novel algorithm that generates all valid minimum-time broadcast schemes by using the recursive structure of hypercubes. Additionally, we compute the total number of valid minimum-time broadcast schemes in hypercubes, which is also the number of all spanning binomial trees. We also give an enumeration of all valid minimum-time broadcast schemes.

APA, Harvard, Vancouver, ISO, and other styles

23

PLATA, OSCAR, TOMAS F. PENA, FRANCISCO F. RIVERA, and EMILIO L. ZAPATA. "AN EFFICIENT PROCESSOR ALLOCATION FOR NESTED PARALLEL LOOPS ON DISTRIBUTED MEMORY HYPERCUBES." Parallel Processing Letters 03, no. 02 (1993): 179–87. http://dx.doi.org/10.1142/s0129626493000228.

Full text

Abstract:

We consider the static processor allocation problem for arbitrarily nested parallel loops on distributed memory, message-passing hypercubes. We present HYPAL (HYpercube Partitioning ALgorithm) as an efficient algorithm to solve this problem. HYPAL calculates an optimal set of partitions of the dimension of the hypercube, and assigns them to the set of iterations of the nested loop. Some considerations about the influence of the communication overhead in order to get a more realistic approach are considered. The main problem at this point is to obtain the communication pattern associated to the parallel program because it depends on scheduling and data distribution.

APA, Harvard, Vancouver, ISO, and other styles

24

Das, Sajal K., Sabine Öhring, and Amit K. Banerjee. "Embeddings into Hyper Petersen Networks: Yet Another Hypercube-Like Interconnection Topology." VLSI Design 2, no. 4 (1995): 335–51. http://dx.doi.org/10.1155/1995/95759.

Full text

Abstract:

A new hypercube-like topology, called the hyper Petersen (HP) network, is proposed and analyzed, which is constructed from the well-known cartesian product of the binary hypercube and the Petersen graph of ten nodes.This topology is an attractive candidate for multiprocessor interconnection having such desirable properties as regularity, high symmetry and connectivity, and logarithmic diameter. For example, an n-dimensional hyper Petersen network, HPn, with N=1.25 * 2n nodes is a regular graph of degree and node-connectivity n and diameter n–1 , whereas an (n–1)-dimensional binary hypercube, Qn−1 , with the same diameter covers only 2n−1 nodes, each of degree (n–1). Thus the HP topology accommodates 2.5 times extra nodes than Qn−1 at the cost of increasing the node-degree by one. With the same degree and connectivity of n, the diameter of the HPn network is one less than that of Qn, yet having 1.25 times larger number of nodes.Efficient routing and broadcasting schemes are presented, and node-disjoint paths in HPn, are computed even under faulty conditions. The versatility of the hyper Petersen networks is emphasized by embedding rings, meshes, hypercubes and several tree-related topologies into it. Contrary to the hypercubes, rings of odd lengths, and a complete binary tree of height n–1 permit subgraph embeddings in HPn.

APA, Harvard, Vancouver, ISO, and other styles

25

LAVAULT, CHRISTIAN. "EMBEDDINGS INTO THE PANCAKE INTERCONNECTION NETWORK." Parallel Processing Letters 12, no. 03n04 (2002): 297–310. http://dx.doi.org/10.1142/s0129626402001002.

Full text

Abstract:

Owing to its nice properties, the pancake is one of the Cayley graphs that were proposed as alternatives to the hypercube for interconnecting processors in parallel computers. In this paper, we present embeddings of rings, grids and hypercubes into the pancake with constant dilation and congestion. We also extend the results to similar efficient embeddings into star graph.

APA, Harvard, Vancouver, ISO, and other styles

26

Nikutta, Robert, Enrique Lopez-Rodriguez, Kohei Ichikawa, et al. "Hypercubes of AGN Tori (HYPERCAT). I. Models and Image Morphology." Astrophysical Journal 919, no. 2 (2021): 136. http://dx.doi.org/10.3847/1538-4357/ac06a6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

TEL, GERARD. "LINEAR ELECTION IN HYPERCUBES." Parallel Processing Letters 05, no. 03 (1995): 357–66. http://dx.doi.org/10.1142/s0129626495000333.

Full text

Abstract:

This article proposes an election algorithm for the hypercube; it exchanges less than [Formula: see text] messages and uses O( log 2 N) time (where N is the size of the cube). A randomized version of the algorithm achieves the same (expected) asymptotic message and time bounds, but uses messages of only O( log log N) bits and can be used in anonymous hypercubes.

APA, Harvard, Vancouver, ISO, and other styles

28

Baumslag, Marc, and Bojana Obrenić. "Index-Shuffle Graphs." International Journal of Foundations of Computer Science 08, no. 03 (1997): 289–304. http://dx.doi.org/10.1142/s0129054197000197.

Full text

Abstract:

Index-shuffle graphs are introduced as candidate interconnection networks for parallel computers. The comparative advantages of index-shuffle graphs over the standard bounded-degree "approximations" of the hypercube, namely butterfly-like and shuffle-like graphs, are demonstrated in the theoretical framework of graph embedding and network emulations. An N-node index-shuffle graph emulates: • an N-node shuffle-exchange graph with no slowdown, which the currently best emulations of shuffle-like graphs by hypercubes and butterflies incur a slowdown of Ω( log N). • its like-sized butterfly graph with a slowdown O( log log log N), while the currently best emulations of butterfly-like graphs by shuffle-like graphs incur a slowdown of Ω( log log N). • an N-node hypercube that executes an on-line leveled algorithm with a slowdown O( log log N), while the slowdown of currently best such emulations of the hypercube by its bounded-degree shuffle-like and butterfly-like derivatives remains Ω( log N). Our emulation is based on an embedding of an N-node hypercube into an N-node index-shuffle graph with dilation O( log log N), while the currently best embeddings of the hypercube into its bounded-degree shuffle-like and butterfly-like derivatives incur a dilation of Ω( log N).

APA, Harvard, Vancouver, ISO, and other styles

29

Dhanalakshmi, R., and C. Durairajan. "r-Identifying codes in binary Hamming space, q-ary Lee space and incomplete hypercube." Discrete Mathematics, Algorithms and Applications 11, no. 02 (2019): 1950027. http://dx.doi.org/10.1142/s1793830919500277.

Full text

Abstract:

We study about monotonicity of [Formula: see text]-identifying codes in binary Hamming space, q-ary Lee space and incomplete hypercube. Also, we give the lower bounds for [Formula: see text] where [Formula: see text] is the smallest cardinality among all [Formula: see text]-identifying codes in [Formula: see text] with respect to the Lee metric. We prove the existence of [Formula: see text]-identifying code in an incomplete hypercube. Also, we give the construction techniques for [Formula: see text]-identifying codes in the incomplete hypercubes in Secs. 4.1 and 4.2. Using these techniques, we give the tables (see Tables 1–6) of upper bounds for [Formula: see text] where [Formula: see text] is the smallest cardinality among all [Formula: see text]-identifying codes in an incomplete hypercube with [Formula: see text] processors. Also, we give the exact values of [Formula: see text] for small values of [Formula: see text] and [Formula: see text] (see Sec. 4.3).

APA, Harvard, Vancouver, ISO, and other styles

30

Wang, Ce. "The uniform measure for quantum walk on hypercube: A quantum Bernoulli noises approach." Journal of Mathematical Physics 63, no. 11 (2022): 113501. http://dx.doi.org/10.1063/5.0070451.

Full text

Abstract:

In this paper, we present a quantum Bernoulli noises approach to quantum walks on hypercubes. We first obtain an alternative description of a general hypercube, and then, based on the alternative description, we find that the operators [Formula: see text] behave actually as the shift operators, where ∂ k and [Formula: see text] are the annihilation and creation operators acting on Bernoulli functionals, respectively. With the above-mentioned operators as the shift operators on the position space, we introduce a discrete-time quantum walk model on a general hypercube and obtain an explicit formula for calculating its probability distribution at any time. We also establish two limit theorems showing that the averaged probability distribution of the walk even converges to the uniform probability distribution. Finally, we show that the walk produces the uniform measure as its stationary measure on the hypercube provided its initial state satisfies some mild conditions. Some other results are also proven.

APA, Harvard, Vancouver, ISO, and other styles

31

Suykens, J. A. K., and L. O. Chua. "n-Double Scroll Hypercubes in 1-D CNNs." International Journal of Bifurcation and Chaos 07, no. 08 (1997): 1873–85. http://dx.doi.org/10.1142/s021812749700145x.

Full text

Abstract:

Unidirectional and diffusive coupling of identical n-double scroll cells in a one-dimensional cellular neural network is studied. Weak coupling between the cells leads to hyperchaos, with n-double scroll hypercube attractors observed in the common state subspace of the cells. Individually the cells remain behaving as n-double scrolls. The n-double scroll hypercubes are filled with multiple scrolls. Their birth goes through the mechanism of intermittency.

APA, Harvard, Vancouver, ISO, and other styles

32

ZIAVRAS, SOTIRIOS G., and MICHALIS A. SIDERAS. "FACILITATING HIGH-PERFORMANCE IMAGE ANALYSIS ON REDUCED HYPERCUBE (RH) PARALLEL COMPUTERS." International Journal of Pattern Recognition and Artificial Intelligence 09, no. 04 (1995): 679–98. http://dx.doi.org/10.1142/s0218001495000262.

Full text

Abstract:

The direct binary hypercube interconnection network has been very popular for the design of parallel computers, because it provides a low diameter and can emulate efficiently the majority of the topologies frequently employed in the development of algorithms. The last fifteen years have seen major efforts to develop image analysis algorithms for hypercube-based parallel computers. The results of these efforts have culminated in a large number of publications included in prestigious scholarly journals and conference proceedings. Nevertheless, the aforementioned powerful properties of the hypercube come at the cost of high VLSI complexity due to the increase in the number of communication ports and channels per PE (processing element) with an increase in the total number of PE’s. The high VLSI complexity of hypercube systems is undoubtedly their dominant drawback; it results in the construction of systems that contain either a large number of primitive PE’s or a small number of powerful PE’s. Therefore, low-dimensional k-ary n-cubes with lower VSLI complexity have recently drawn the attention of many designers of parallel computers. Alternative solutions reduce the hypercube’s VLSI complexity without jeopardizing its performance. Such an effort by Ziavras has resulted in the introduction of reduced hypercubes (RH’s). Taking advantage of existing high-performance routing techniques, such as wormhole routing, an RH is obtained by a uniform reduction in the number of edges for each hypercube node. An RH can also be viewed as several connected copies of the well-known cube-connected-cycles network. The objective here is to prove that parallel computers comprising RH interconnection networks are definitely good choices for all levels of image analysis. Since the exact requirements of high-level image analysis are difficult to identify, but it is believed that versatile interconnection networks, such as the hypercube, are suitable for relevant tasks, we investigate the problem of emulating hypercubes on RH’s. The ring (or linear array), the torus (or mesh), and the binary tree are the most frequently used topologies for the development of algorithms in low-level and intermediate-level image analysis. Thus, to prove the viability of the RH for the two lower levels of image analysis, we introduce techniques for embedding the aforementioned three topologies into RH’s. The results prove the suitability of RH’s for all levels of image analysis.

APA, Harvard, Vancouver, ISO, and other styles

33

Markovski, Smile, and Aleksandra Mileva. "On construction of orthogonal d-ary operations." Publications de l'Institut Math?matique (Belgrade) 101, no. 115 (2017): 109–19. http://dx.doi.org/10.2298/pim1715109m.

Full text

Abstract:

A d-hypercube of order n is an n x ... x nd (d times) array with nd elements from a set Q of cardinality n. We recall several connections between d-hypercubes of order n and d-ary operations of order n. We give constructions of orthogonal d-ary operations that generalize a result of Belyavskaya and Mullen. Our main result is a general construction of d-orthogonal d-ary operations from d-ary quasigroups.

APA, Harvard, Vancouver, ISO, and other styles

34

Cho, Yunhi, and Seonhwa Kim. "Volume of Hypercubes Clipped by Hyperplanes and Combinatorial Identities." Electronic Journal of Linear Algebra 36, no. 36 (2020): 228–55. http://dx.doi.org/10.13001/ela.2020.5085.

Full text

Abstract:

There is an elegant expression for the volume of hypercube $[0,1]^n$ clipped by a single hyperplane. In the article, the formula is generalized to the case of more than one hyperplane. An important foundation for the result is Lawrence's formula and a way to weaken two restrictions of simplicity and non-parallelness in his formula is also considered. Several concrete volume formulas of clipped hypercubes are derived explicitly and the corresponding combinatorial identities are obtained as an application.

APA, Harvard, Vancouver, ISO, and other styles

35

You, Lantao, Jianfeng Jiang, and Yuejuan Han. "Super Spanning Connectivity of the Folded Divide-and-SwapCube." Mathematics 11, no. 11 (2023): 2581. http://dx.doi.org/10.3390/math11112581.

Full text

Abstract:

A k*-container of a graph G is a set of k disjoint paths between any pair of nodes whose union covers all nodes of G. The spanning connectivity of G, κ*(G), is the largest k, such that there exists a j*-container between any pair of nodes of G for all 1≤j≤k. If κ*(G)=κ(G), then G is super spanning connected. Spanning connectivity is an important property to measure the fault tolerance of an interconnection network. The divide-and-swap cube DSCn is a newly proposed hypercube variant, which reduces the network cost from O(n2) to O(nlog2n) compared with the hypercube and other hypercube variants. The folded divide-and-swap cube FDSCn is proposed based on DSCn to reduce the diameter of DSCn. Both DSCn and FDSCn possess many better properties than hypercubes. In this paper, we investigate the super spanning connectivity of FDSCn where n=2d and d≥1. We show that κ*(FDSCn)=κ(FDSCn)=d+2, which means there exists an m-DPC(node-disjoint path cover) between any pair of nodes in FDSCn for all 1≤m≤d+2.

APA, Harvard, Vancouver, ISO, and other styles

36

Chen, Liang, Caiming Zhong, and Zehua Zhang. "Explanation of clustering result based on multi-objective optimization." PLOS ONE 18, no. 10 (2023): e0292960. http://dx.doi.org/10.1371/journal.pone.0292960.

Full text

Abstract:

Clustering is an unsupervised machine learning technique whose goal is to cluster unlabeled data. But traditional clustering methods only output a set of results and do not provide any explanations of the results. Although in the literature a number of methods based on decision tree have been proposed to explain the clustering results, most of them have some disadvantages, such as too many branches and too deep leaves, which lead to complex explanations and make it difficult for users to understand. In this paper, a hypercube overlay model based on multi-objective optimization is proposed to achieve succinct explanations of clustering results. The model designs two objective functions based on the number of hypercubes and the compactness of instances and then uses multi-objective optimization to find a set of nondominated solutions. Finally, an Utopia point is defined to determine the most suitable solution, in which each cluster can be covered by as few hypercubes as possible. Based on these hypercubes, an explanations of each cluster is provided. Upon verification on synthetic and real datasets respectively, it shows that the model can provide a concise and understandable explanations to users.

APA, Harvard, Vancouver, ISO, and other styles

37

BOSSARD, ANTOINE. "ON THE DECYCLING PROBLEM IN HIERARCHICAL HYPERCUBES." Journal of Interconnection Networks 14, no. 02 (2013): 1350006. http://dx.doi.org/10.1142/s0219265913500060.

Full text

Abstract:

Due to the huge number of CPU nodes involved in modern supercomputers, efficient CPU connection is challenging, and legacy simple network topologies such as hypercubes are no more suitable for physical reasons. The hierarchical hypercube (HHC) has been designed as a topology for interconnection network of massively parallel systems. An HHC is effectively able to link many nodes while retaining a low degree and a small diameter compared to a hypercube of the same size. In this paper, we address a fundamental problem inside an HHC, the decycling problem, which consists of finding a set of nodes as small as possible such that excluding these nodes from the network ensures a cycle-free topology. This problem has many important applications such as lock-free resource allocation and concurrent access. So, we propose in this paper an efficient algorithm finding in an HHC a decycling set of competitively small size.

APA, Harvard, Vancouver, ISO, and other styles

38

BAL, DEEPAK, ANTHONY BONATO, WILLIAM B. KINNERSLEY, and PAWEŁ PRAŁAT. "Lazy Cops and Robbers on Hypercubes." Combinatorics, Probability and Computing 24, no. 6 (2015): 829–37. http://dx.doi.org/10.1017/s0963548314000807.

Full text

Abstract:

We consider a variant of the game of Cops and Robbers, called Lazy Cops and Robbers, where at most one cop can move in any round. We investigate the analogue of the cop number for this game, which we call the lazy cop number. Lazy Cops and Robbers was recently introduced by Offner and Ojakian, who provided asymptotic upper and lower bounds on the lazy cop number of the hypercube. By coupling the probabilistic method with a potential function argument, we improve on the existing lower bounds for the lazy cop number of hypercubes.

APA, Harvard, Vancouver, ISO, and other styles

39

Kang, Yingli, Shuai Ye, Weidong Fu, and Jing Zhu. "The Pessimistic Diagnosability of Folded Petersen Cubes." Journal of Mathematics 2022 (October 20, 2022): 1–9. http://dx.doi.org/10.1155/2022/3114022.

Full text

Abstract:

Diagnosability is an important metric parameter for measuring the reliability of multiprocessor systems. The pessimistic diagnosis strategy is a classic diagnostic model based on the PMC model. The class of folded Petersen cubes, denoted by FP Q n , k , where n , k ≥ 0 and n , k ≠ 0 , 0 , is introduced as a competitive model of the hypercubes, which is constructed by iteratively applying the Cartesian product operation on the hypercube Q n and the Petersen graph P . In this paper, by exploring the structural properties of the folded Petersen cubes FP Q n , k , we first prove that FP Q n , k is n + 3 k diagnosable under the PMC model. Then, we completely derive that the pessimistic diagnosability of FP Q n , k is 2 n + 6 k − 2 under the PMC model. Furthermore, the diagnosability and the pessimistic diagnosability of the class of folded Petersen cubes, including the hypercube, folded Petersen graph, and hyper Petersen graph, are obtained.

APA, Harvard, Vancouver, ISO, and other styles

40

Nikutta, Robert, Enrique Lopez-Rodriguez, Kohei Ichikawa, et al. "Hypercubes of AGN Tori (HYPERCAT). II. Resolving the Torus with Extremely Large Telescopes." Astrophysical Journal 923, no. 1 (2021): 127. http://dx.doi.org/10.3847/1538-4357/ac2949.

Full text

Abstract:

Abstract Recent infrared interferometric observations revealed sub-parsec scale dust distributions around active galactic nuclei (AGNs). Using images of Clumpy torus models and NGC 1068 as an example, we demonstrate that the near- and mid-infrared nuclear emission of some nearby AGNs will be resolvable in direct imaging with the next generation of 30 m telescopes, potentially breaking degeneracies from previous studies that used integrated spectral energy distributions of unresolved AGN tori. To that effect we model wavelength-dependent point spread functions from the pupil images of various telescopes: James Webb Space Telescope, Keck, Giant Magellan Telescope, Thirty Meter Telescope, and Extremely Large Telescope. We take into account detector pixel scales and noise, and apply deconvolution techniques for image recovery. We also model 2D maps of the 10 μm silicate feature strength, S 10, of NGC 1068 and compare with observations. When the torus is resolved, we find S 10 variations across the image. However, to reproduce the S 10 measurements of an unresolved torus a dusty screen of A V > 9 mag is required. We also fit the first resolved image of the K-band emission in NGC 1068 recently published by the GRAVITY Collaboration, deriving likely model parameters of the underlying dust distribution. We find that both (1) an elongated structure suggestive of a highly inclined emission ring, and (2) a geometrically thin but optically thick flared disk where the emission arises from a narrow strip of hot cloud surface layers on the far inner side of the torus funnel, can explain the observations.

APA, Harvard, Vancouver, ISO, and other styles

41

Thieulot, Cedric, and Wolfgang Bangerth. "On the choice of finite element for applications in geodynamics – Part 2: A comparison of simplex and hypercube elements." Solid Earth 16, no. 6 (2025): 457–76. https://doi.org/10.5194/se-16-457-2025.

Full text

Abstract:

Abstract. Many geodynamical models are formulated in terms of the Stokes equations that are then coupled to other equations. For the numerical solution of the Stokes equations, geodynamics codes over the past decades have used essentially every finite element that has ever been proposed for the solution of this equation, on both triangular/tetrahedral (“simplex”) and quadrilaterals/hexahedral (“hypercube”) meshes. However, in many and perhaps most cases, the specific choice of element does not seem to have been the result of careful benchmarking efforts but based on implementation efficiency or the implementers' background. In a first part of this paper (Thieulot and Bangerth, 2022), we have provided a comprehensive comparison of the accuracy and efficiency of the most widely used hypercube elements for the Stokes equations. We have done so using a number of benchmarks that illustrate “typical” geodynamic situations, specifically taking into account spatially variable viscosities. Our findings there showed that only Taylor–Hood-type elements with either continuous (Q2×Q1) or discontinuous (Q2×P-1) pressure are able to adequately and efficiently approximate the solution of the Stokes equations. In this, the second part of this work, we extend the comparison to simplex meshes. In particular, we compare triangular Taylor–Hood elements against the MINI element and one often referred to as the “Crouzeix–Raviart” element. We compare these choices against the accuracy obtained on hypercube Taylor–Hood elements with approximately the same computational cost. Our results show that, like on hypercubes, the Taylor–Hood element is substantially more accurate and efficient than the other choices. Our results also indicate that hypercube meshes yield slightly more accurate results than simplex meshes but that the difference is relatively small and likely unimportant given that hypercube meshes often lead to slightly denser (and consequently more expensive) matrices.

APA, Harvard, Vancouver, ISO, and other styles

42

Kuo, Che-Nan. "Every edge lies on cycles embedding in folded hypercubes with both vertex and edge faults." Discrete Mathematics, Algorithms and Applications 08, no. 01 (2016): 1650001. http://dx.doi.org/10.1142/s1793830916500014.

Full text

Abstract:

The folded hypercube is a well-known variation of hypercube structure and can be constructed from a hypercube by adding an edge to every pair of vertices with complementary addresses. Let [Formula: see text] (respectively, [Formula: see text]) denote the set of faulty vertices (respectively, faulty edges) in an [Formula: see text]-dimensional folded hypercube [Formula: see text]. In the case that all edges in [Formula: see text] are fault-free, Cheng et al. [Cycles embedding on folded hypercubes with faulty vertices, Discrete Appl. Math. 161 (2013) 2894–2900] has shown that (1) every fault-free edge of [Formula: see text] lies on a fault-free cycle of every even length from [Formula: see text] to [Formula: see text] if [Formula: see text], where [Formula: see text]; and (2) every fault-free edge of [Formula: see text] lies on a fault-free cycle of every odd length from [Formula: see text] to [Formula: see text] if [Formula: see text], where [Formula: see text] is even. In this paper, we extend Cheng’s result to obtain two further properties, which consider both vertex and edge faults, as follows: (1) Every fault-free edge of [Formula: see text] lies on a fault-free cycle of every even length from [Formula: see text] to [Formula: see text] if [Formula: see text], where [Formula: see text]; (2) Every fault-free edge of [Formula: see text] lies on a fault-free cycle of every odd length from [Formula: see text] to [Formula: see text] if [Formula: see text], where [Formula: see text] is even.

APA, Harvard, Vancouver, ISO, and other styles

43

ZIAVRAS, SOTIRIOS G., and MUKUND P. KHATRI. "Binary trees of modified hypercubes: a family of networks for hypercube-like parallel computers." International Journal of Electronics 76, no. 1 (1994): 27–36. http://dx.doi.org/10.1080/00207219408925903.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Lü, Huazhong, and Tingzeng Wu. "On the conjecture of bijection between perfect matching and sub-hypercube in folded hypercubes." Discrete Applied Mathematics 279 (May 2020): 192–94. http://dx.doi.org/10.1016/j.dam.2019.08.017.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Seo, Jung-Hyun, and Hyeong-Ok Lee. "Design and Analysis of a Symmetric Log Star Graph with a Smaller Network Cost Than Star Graphs." Electronics 10, no. 8 (2021): 981. http://dx.doi.org/10.3390/electronics10080981.

Full text

Abstract:

Graphs are used as models to solve problems in fields such as mathematics, computer science, physics, and chemistry. In particular, torus, hypercube, and star graphs are popular when modeling the connection structure of processors in parallel computing because they are symmetric and have a low network cost. Whereas a hypercube has a substantially smaller diameter than a torus, star graphs have been presented as an alternative to hypercubes because of their lower network cost. We propose a novel log star (LS) that is symmetric and has a lower network cost than a star graph. The LS is an undirected, recursive, and regular graph. In LSn, the number of nodes is n! while the degree is 2log2n − 1 and the diameter is 0.5n(log2n)2 + 0.75nlog2n. In this study, we analyze the basic topological properties of LS. We prove that LSn is a symmetrical connected graph and analyzed its subgraph characteristics. Then, we propose a routing algorithm and derive the diameter and network cost. Finally, the network costs of the LS and star graph-like networks are compared.

APA, Harvard, Vancouver, ISO, and other styles

46

Padmavathi, SV, and K. Krishnan. "Weak Convex Domination in Hypercubes." Shanlax International Journal of Arts, Science and Humanities 8, S1-May (2021): 50–53. http://dx.doi.org/10.34293/sijash.v8is1-may.4507.

Full text

Abstract:

The n-cube Qn is the graph whose vertex set is the set of all n-dimensional Boolean vectors, two vertices being joined if and only if they differ in exactly one coordinate. The n-star graph Sn is a simple graph whose vertex set is the set of all n! permutations of {1, 2, · · · , n} and two vertices α and β are adjacent if and only if α(1)≠β(1) and α(i) ≠β(i) for exactly one i, i≠ 1. In this paper we determine weak convex domination number for hypercubes. Also convex, weak convex, m - convex and l1-convex numbers of star and hypercube graphs are determined.

APA, Harvard, Vancouver, ISO, and other styles

47

STEWART, IAIN A. "DISTRIBUTED ALGORITHMS FOR BUILDING HAMILTONIAN CYCLES IN k-ARY n-CUBES AND HYPERCUBES WITH FAULTY LINKS." Journal of Interconnection Networks 08, no. 03 (2007): 253–84. http://dx.doi.org/10.1142/s0219265907002016.

Full text

Abstract:

We derive a sequential algorithm Find-Ham-Cycle with the following property. On input: k and n (specifying the k-ary n-cube [Formula: see text]); F, a set of at most 2n − 2 faulty links; and v , a node of [Formula: see text], the algorithm outputs nodes v + and v − such that if Find-Ham-Cycle is executed once for every node v of [Formula: see text] then the node v + (resp. v −) denotes the successor (resp. predecessor) node of v on a fixed Hamiltonian cycle in [Formula: see text] in which no link is in F. Moreover, the algorithm Find-Ham-Cycle runs in time polynomial in n and log k. We also obtain a similar algorithm for an n-dimensional hypercube with at most n − 2 faulty links. We use our algorithms to obtain distributed algorithms to embed Hamiltonian cycles k-ary n-cubes and hypercubes with faulty links; our hypercube algorithm improves on a recently-derived algorithm due to Leu and Kuo, and our k-ary n-cube algorithm is the first distributed algorithm for embedding a Hamiltonian cycle in a k-ary n-cube with faulty links.

APA, Harvard, Vancouver, ISO, and other styles

48

Pai, Kung-Jui. "Three Edge-Disjoint Hamiltonian Cycles in Folded Locally Twisted Cubes and Folded Crossed Cubes with Applications to All-to-All Broadcasting." Mathematics 11, no. 15 (2023): 3384. http://dx.doi.org/10.3390/math11153384.

Full text

Abstract:

All-to-all broadcasting means to distribute the exclusive message of each node in the network to all other nodes. It can be handled by rings, and a Hamiltonian cycle is a ring that visits each vertex exactly once. Multiple edge-disjoint Hamiltonian cycles, abbreviated as EDHCs, have two application advantages: (1) parallel data broadcast and (2) edge fault-tolerance in network communications. There are three edge-disjoint Hamiltonian cycles on n-dimensional locally twisted cubes and n-dimensional crossed cubes while n ≥ 6, respectively. Locally twisted cubes, crossed cubes, folded locally twisted cubes (denoted as FLTQn), and folded crossed cubes (denoted as FCQn) are among the hypercube-variant network. The topology of hypercube-variant network has more wealth than normal hypercubes in network properties. Then, the following results are presented in this paper: (1) Using the technique of edge exchange, three EDHCs are constructed in FLTQ5 and FCQ5, respectively. (2) According to the recursive structure of FLTQn and FCQn, there are three EDHCs in FLTQn and FCQn while n ≥ 6. (3) Considering that multiple faulty edges will occur randomly, the data broadcast performance of three EDHCs in FLTQn and FCQn is evaluated by simulation when 5 ≤ n ≤ 9.

APA, Harvard, Vancouver, ISO, and other styles

49

Mukhopadhyay, Priyanka. "Faster Provable Sieving Algorithms for the Shortest Vector Problem and the Closest Vector Problem on Lattices in ℓp Norm". Algorithms 14, № 12 (2021): 362. http://dx.doi.org/10.3390/a14120362.

Full text

Abstract:

In this work, we give provable sieving algorithms for the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP) on lattices in ℓp norm (1≤p≤∞). The running time we obtain is better than existing provable sieving algorithms. We give a new linear sieving procedure that works for all ℓp norm (1≤p≤∞). The main idea is to divide the space into hypercubes such that each vector can be mapped efficiently to a sub-region. We achieve a time complexity of 22.751n+o(n), which is much less than the 23.849n+o(n) complexity of the previous best algorithm. We also introduce a mixed sieving procedure, where a point is mapped to a hypercube within a ball and then a quadratic sieve is performed within each hypercube. This improves the running time, especially in the ℓ2 norm, where we achieve a time complexity of 22.25n+o(n), while the List Sieve Birthday algorithm has a running time of 22.465n+o(n). We adopt our sieving techniques to approximation algorithms for SVP and CVP in ℓp norm (1≤p≤∞) and show that our algorithm has a running time of 22.001n+o(n), while previous algorithms have a time complexity of 23.169n+o(n).

APA, Harvard, Vancouver, ISO, and other styles

50

PANAGIOTOU, KONSTANTINOS, XAVIER PÉREZ-GIMÉNEZ, THOMAS SAUERWALD, and HE SUN. "Randomized Rumour Spreading: The Effect of the Network Topology." Combinatorics, Probability and Computing 24, no. 2 (2014): 457–79. http://dx.doi.org/10.1017/s0963548314000194.

Full text

Abstract:

We consider the popular and well-studied push model, which is used to spread information in a given network with n vertices. Initially, some vertex owns a rumour and passes it to one of its neighbours, which is chosen randomly. In each of the succeeding rounds, every vertex that knows the rumour informs a random neighbour. It has been shown on various network topologies that this algorithm succeeds in spreading the rumour within O(log n) rounds. However, many studies are quite coarse and involve huge constants that do not allow for a direct comparison between different network topologies. In this paper, we analyse the push model on several important families of graphs, and obtain tight runtime estimates. We first show that, for any almost-regular graph on n vertices with small spectral expansion, rumour spreading completes after log2n + log n+o(log n) rounds with high probability. This is the first result that exhibits a general graph class for which rumour spreading is essentially as fast as on complete graphs. Moreover, for the random graph G(n,p) with p=c log n/n, where c > 1, we determine the runtime of rumour spreading to be log2n + γ (c)log n with high probability, where γ(c) = clog(c/(c−1)). In particular, this shows that the assumption of almost regularity in our first result is necessary. Finally, for a hypercube on n=2d vertices, the runtime is with high probability at least (1+β) ⋅ (log2n + log n), where β > 0. This reveals that the push model on hypercubes is slower than on complete graphs, and thus shows that the assumption of small spectral expansion in our first result is also necessary. In addition, our results combined with the upper bound of O(log n) for the hypercube (see [11]) imply that the push model is faster on hypercubes than on a random graph G(n, clog n/n), where c is sufficiently close to 1.

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Hypercuts'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles