Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/SMAWK_algorithm> ?p ?o }
Showing triples 1 to 38 of
38
with 100 triples per page.
- SMAWK_algorithm abstract "The SMAWK algorithm is an algorithm for finding the minimum value in each row of an implicitly-defined totally monotone matrix. It is named after the initials of its five inventors, Peter Shor, Shlomo Moran, Alok Aggarwal, Robert Wilber, and Maria Klawe.For the purposes of this algorithm, a matrix is defined to be monotone if each row's minimum value occurs in a column which is equal to or greater than the column of the previous row's minimum. It is totally monotone if the same property is true for every submatrix (defined by an arbitrary subset of the rows and columns of the given matrix). Equivalently, a matrix is totally monotone if there does not exist a 2×2 submatrix whose row minima are in the top right and bottom left corners. Every Monge array is totally monotone, but not necessarily vice versa.For the SMAWK algorithm, the matrix to be searched should be defined as a function, and this function is given as input to the algorithm (together with the dimensions of the matrix). The algorithm then evaluates the function whenever it needs to know the value of a particular matrix cell. If this evaluation takes O(1), then, for a matrix with r rows and c columns, the running time and number of function evaluations are both O(c(1 + log(r/c))). This is much faster than the O(rc) time of a naive algorithm that evaluates all matrix cells.The main applications of this method presented in the original paper by Aggarwal et al. were in computational geometry, in finding the farthest point from each point of a convex polygon, and in finding optimal enclosing polygons. Subsequent research found applications of the same algorithm in breaking paragraphs into lines, RNA secondary structure prediction, DNA and protein sequence alignment, the construction of prefix codes, and image thresholding, among others.".
- SMAWK_algorithm wikiPageID "40077712".
- SMAWK_algorithm wikiPageLength "4820".
- SMAWK_algorithm wikiPageOutDegree "17".
- SMAWK_algorithm wikiPageRevisionID "634167020".
- SMAWK_algorithm wikiPageWikiLink Algorithm.
- SMAWK_algorithm wikiPageWikiLink Category:Combinatorial_algorithms.
- SMAWK_algorithm wikiPageWikiLink Category:Matrix_theory.
- SMAWK_algorithm wikiPageWikiLink Computational_geometry.
- SMAWK_algorithm wikiPageWikiLink DNA.
- SMAWK_algorithm wikiPageWikiLink Line_wrap_and_word_wrap.
- SMAWK_algorithm wikiPageWikiLink Maria_Klawe.
- SMAWK_algorithm wikiPageWikiLink Matrix_(mathematics).
- SMAWK_algorithm wikiPageWikiLink Monge_array.
- SMAWK_algorithm wikiPageWikiLink Nucleic_acid_secondary_structure.
- SMAWK_algorithm wikiPageWikiLink Peter_Shor.
- SMAWK_algorithm wikiPageWikiLink Prefix_code.
- SMAWK_algorithm wikiPageWikiLink Protein.
- SMAWK_algorithm wikiPageWikiLink RNA.
- SMAWK_algorithm wikiPageWikiLink Sequence_alignment.
- SMAWK_algorithm wikiPageWikiLink Shlomo_Moran.
- SMAWK_algorithm wikiPageWikiLink Thresholding_(image_processing).
- SMAWK_algorithm wikiPageWikiLink Word_wrap.
- SMAWK_algorithm wikiPageWikiLinkText "SMAWK algorithm".
- SMAWK_algorithm hasPhotoCollection SMAWK_algorithm.
- SMAWK_algorithm wikiPageUsesTemplate Template:Algorithm-stub.
- SMAWK_algorithm wikiPageUsesTemplate Template:Reflist.
- SMAWK_algorithm subject Category:Combinatorial_algorithms.
- SMAWK_algorithm subject Category:Matrix_theory.
- SMAWK_algorithm hypernym Algorithm.
- SMAWK_algorithm type Software.
- SMAWK_algorithm comment "The SMAWK algorithm is an algorithm for finding the minimum value in each row of an implicitly-defined totally monotone matrix. It is named after the initials of its five inventors, Peter Shor, Shlomo Moran, Alok Aggarwal, Robert Wilber, and Maria Klawe.For the purposes of this algorithm, a matrix is defined to be monotone if each row's minimum value occurs in a column which is equal to or greater than the column of the previous row's minimum.".
- SMAWK_algorithm label "SMAWK algorithm".
- SMAWK_algorithm sameAs m.0wfzg8j.
- SMAWK_algorithm sameAs Q17103377.
- SMAWK_algorithm sameAs Q17103377.
- SMAWK_algorithm wasDerivedFrom SMAWK_algorithm?oldid=634167020.
- SMAWK_algorithm isPrimaryTopicOf SMAWK_algorithm.