Wyniki wyszukiwania - Biblioteka Nauki

Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl

Ograniczanie wyników

Znaleziono wyników: 6

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: polynomial time algorithm

Sortuj według:

Ogranicz wyniki do:

Polynomial Time Algorithms for Variants of Graph Matching on Partial k-Trees

100%

Nagoya T.

Foundations of Computing and Decision Sciences

2016

tom Vol. 41, No. 3

163--181

In this paper, we deal with two variants of graph matching, the graph isomorphism with restriction and the preﬁx set of graph isomorphism. The former problem is known to be NP-complete, whereas the latter problem is known to be GI-complete. We propose polynomial time exact algorithms for these problems on partial k-trees.

A Batching Machine Model for Lot Scheduling on a Single Machine

88%

Kovalyov M. Y.

Foundations of Computing and Decision Sciences

2018

tom Vol. 43, No. 1

38--40

A recently introduced lot scheduling problem is considered. It is to find a partition of jobs of n orders into lots and to sequence these lots on a single machine so that the total average completion time of the orders is minimized. A simple O(n log n) time algorithm is presented for this problem in the literature, with a relatively sophisticated proof of its optimality. We show that modeling this problem as a classic batching machine problem makes its optimal solution obvious.

Reconstructing Binary Matrices under Window Constraints from their Row and Column Sums

75%

Alpers A. , Gritzmann P.

Fundamenta Informaticae

2017

tom Vol. 155, nr 4

321--340

The present paper deals with the discrete inverse problem of reconstructing binary matrices from their row and column sums under additional constraints on the number and pattern of entries in specified minors. While the classical consistency and reconstruction problems for two directions in discrete tomography can be solved in polynomial time, it turns out that these window constraints cause various unexpected complexity jumps back and forth from polynomialtime solvability to NP-hardness.

On Computing Discrete Logarithms in Bulk and Randomness Extractors

75%

Durnoga K. , Źrałek B.

Fundamenta Informaticae

2015

tom Vol. 141, nr 4

345--366

We prove several results of independent interest related to the problem of computing deterministically discrete logarithms in a finite field. The motivation was to give a number-theoretic construction of a non-malleable extractor improving the solution from the recent paper Privacy Amplification and Non-Malleable Extractors via Character Sums by Dodis et al. There, the authors provide the first explicit example of a non-malleable extractor – a cryptographic primitive that significantly strengthens the notion of a classical randomness extractor. In order to make the extractor robust, so that it runs in polynomial time and outputs a linear number of bits, they rely on a certain conjecture on the least prime in a residue class. In this work we present a modification of their construction that allows to remove that dependency and address an issue we identified in the original development. Namely, it required an additional assumption about feasibility of finding a primitive element of a finite field. As an auxiliary result, we show an efficiently computable bijection between any order M subgroup of the multiplicative group of a finite field and a set of integers modulo M with the provision that M is a smooth number. Also, we provide a version of the baby-step giantstep method for solving multiple instances of the discrete logarithm problem in the multiplicative group of a prime field. It performs better than the generic algorithm when run on a machine without constant-time access to each memory cell, e.g., on a classical Turing machine.

A fast and simple algorithm for computing m-shortest paths in stage graph

63%

Sherwood M. , Gewali L. , Selvaraj H. , Muthukumar V.

Systems Science

2004

tom Vol. 30, no 1

91-97

We consider the problem of computing m shortest paths between a source node s and a target node t in a stage graph. Polynomial time algorithms known to solve this problem use complicated data structures. This paper proposes a very simple algorithm for computing all m shortest paths in a stage graph efficiently. The proposed algorithm does not use any complicated data structure and can be implemented in a straightforward way by using only array data structure. This problem appears as a sub-problem for planning risk reduced multiple k-legged trajectories for aerial vehicles.

Złożoność obliczeniowa problemu szeregowania zadań w cylindrycznym systemie przepływowym

51%

Nadolski A.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

2006

tom z. 143

99-105

W pracy rozważamy złożoność obliczeniową szeregowania zadań w cylindrycznym systemie przepływowym. Konstruujemy algorytm wielomianowy dla problemu dwumaszynowego oraz wykazujemy, że problem staje się NP-trudny przy szeregowaniu na trzech maszynach oraz na dwóch maszynach przy wymuszeniu braku obustronnych przestojów.

We consider the scheduling problem in a cylindrical flow shop to minimize the cycle time. We provide a polynomial time algorithm in the case of two processors and prove that the problem becomes NP-hard in the case of three processors. Moreover, we show that scheduling with no-wait and no-idle constraints is NP-hard in the case of two processors.