4 results
Search Results
2. Webster sequences, apportionment problems, and just-in-time sequencing.
- Author
-
Li, Xiaomin
- Subjects
- *
MATHEMATICS , *ALGORITHMS , *PARALLEL algorithms , *INTEGERS , *PARTITIONS (Mathematics) - Abstract
Given a real number α ∈ (0 , 1) , we define the Webster sequence of density α to be W α = (⌈ (n − 1 / 2) / α ⌉) n ∈ N , where ⌈ x ⌉ is the ceiling function. It is known that if α and β are irrational with α + β = 1 , then W α and W β partition N. On the other hand, an analogous result for three-part partitions does not hold: There does not exist a partition of N into sequences W α , W β , W γ with α , β , γ irrational. In this paper, we consider the question of how close one can come to a three-part partition of N into Webster sequences with prescribed densities α , β , γ. We show that if α , β , γ are irrational with α + β + γ = 1 , there exists a partition of N into sequences of densities α , β , γ , in which one of the sequences is a Webster sequence and the other two are "almost" Webster sequences that are obtained from Webster sequences by perturbing some elements by at most 1. We also provide two efficient algorithms to construct such partitions. The first algorithm outputs the n th element of each sequence in O (1) time and the second algorithm gives the assignment of the m th positive integer to a sequence in O (1) time. We show that the results are best-possible in several respects. Moreover, we describe applications of these results to apportionment and optimal scheduling problems. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
3. Investigating results and performance of search and construction algorithms for word-based LFSRs, [formula omitted]-LFSRs.
- Author
-
Bishoi, Susil Kumar and Matyas, Vashek
- Subjects
- *
ALGORITHMS , *SEARCH algorithms , *POLYNOMIALS , *MATHEMATICS , *MATHEMATICAL analysis - Abstract
Linear feedback shift registers (LFSRs) play a significant role in communications security and we investigate design of a selected class of word-based LFSRs known as σ -LFSRs. Both the search algorithm and the construction algorithm generate efficient primitive σ -LFSRs. The search algorithm first constructs the σ -polynomial and then checks the primitiveness of the σ -polynomial, whereas the construction algorithm for the σ -LFSR, first finds a primitive polynomial f ( x ) and then constructs the primitive σ -LFSR from f ( x ) . In this paper, we present some novel results pertaining to the search algorithm for primitive σ -LFSR along with the exhaustive search space complexity of the search algorithm for σ -LFSRs. Then we investigate and compare the performance of the construction algorithm with the search algorithm for the primitive σ -LFSR. Finally, the number of σ -LFSRs similar to the σ -LFSRs generated by the construction algorithm is provided. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
4. Threshold-coloring and unit-cube contact representation of planar graphs
- Author
-
Stephen G. Kobourov, Michael Kaufmann, Jackson Toeniskoetter, Sergey Pupyrev, Steven Chaplick, Md. Jawaherul Alam, and Gašper Fijavž
- Subjects
THRESHOLD-COLORING ,COLORIMETRY ,COLORING PROBLEMS ,0102 computer and information sciences ,02 engineering and technology ,POLYNOMIAL APPROXIMATION ,GRAPH THEORY ,01 natural sciences ,NP-COMPLETENESS ,Combinatorics ,Indifference graph ,Chordal graph ,0202 electrical engineering, electronic engineering, information engineering ,Discrete Mathematics and Combinatorics ,COLOR ,Graph coloring ,GRAPH COLORING ,GRAPH-THEORETIC PROBLEM ,Mathematics ,Discrete mathematics ,TREES (MATHEMATICS) ,PLANAR GRAPH ,Book embedding ,Clique-sum ,GEOMETRY ,Applied Mathematics ,ALGORITHMS ,COLOR DIFFERENCE ,Complete coloring ,GRAPH COLORINGS ,1-planar graph ,POLYNOMIAL-TIME ALGORITHMS ,Edge coloring ,PLANAR GRAPHS ,UNIT-CUBE CONTACT REPRESENTATION ,010201 computation theory & mathematics ,COLORING ,020201 artificial intelligence & image processing ,GRAPHIC METHODS ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
In this paper we study threshold-coloring of graphs, where the vertex colors represented by integers are used to describe any spanning subgraph of the given graph as follows. A pair of vertices with a small difference in their colors implies that the edge between them is present, while a pair of vertices with a big color difference implies that the edge is absent. Not all planar graphs are threshold-colorable, but several subclasses, such as trees, some planar grids, and planar graphs with no short cycles can always be threshold-colored. Using these results we obtain unit-cube contact representation of several subclasses of planar graphs. Variants of the threshold-coloring problem are related to well-known graph coloring and other graph-theoretic problems. Using these relations we show the NP-completeness for two of these variants, and describe a polynomial-time algorithm for another. (C) 2015 Elsevier B.V. All rights reserved.
- Published
- 2017
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.