|
Kernelization
In computer science, a kernelization is a technique for designing efficient algorithms that achieve their efficiency by a preprocessing stage in which inputs to the algorithm are replaced by a smaller input, called a "kernel". The result of solving the problem on the kernel should either be the same as on the original input, or it should be easy to transform the output on the kernel to the desired output for the original problem. Kernelization is often achieved by applying a set of reduction rules that cut away parts of the instance that are easy to handle. In parameterized complexity theory, it is often possible to prove that a kernel with guaranteed bounds on the size of a kernel (as a function of some parameter associated to the problem) can be found in polynomial time. When this is possible, it results in a fixed-parameter tractable algorithm whose running time is the sum of the (polynomial time) kernelization step and the (non-polynomial but bounded by the parameter) time to ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bidimensionality
Bidimensionality theory characterizes a broad range of graph problems (bidimensional) that admit efficient approximate, fixed-parameter or kernel solutions in a broad range of graphs. These graph classes include planar graphs, map graphs, bounded-genus graphs and graphs excluding any fixed minor. In particular, bidimensionality theory builds on the graph minor theory of Robertson and Seymour by extending the mathematical results and building new algorithmic tools. The theory was introduced in the work of Demaine, Fomin, Hajiaghayi, and Thilikos, for which the authors received the Nerode Prize in 2015. Definition A parameterized problem \Pi is a subset of \Gamma^\times \mathbb for some finite alphabet \Gamma. An instance of a parameterized problem consists of ''(x,k)'', where ''k'' is called the parameter. A parameterized problem \Pi is ''minor-bidimensional'' if # For any pair of graphs H,G, such that H is a minor of G and integer k, (G,k)\in \Pi yields that (H,k)\i ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Parameterized Complexity
In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. The complexity of a problem is then measured as a function of those parameters. This allows the classification of NP-hard problems on a finer scale than in the classical setting, where the complexity of a problem is only measured as a function of the number of bits in the input. The first systematic work on parameterized complexity was done by . Under the assumption that P ≠ NP, there exist many natural problems that require superpolynomial running time when complexity is measured in terms of the input size only, but that are computable in a time that is polynomial in the input size and exponential or worse in a parameter . Hence, if is fixed at a small value and the growth of the function over is relatively small then such p ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Parameterized Complexity
In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. The complexity of a problem is then measured as a function of those parameters. This allows the classification of NP-hard problems on a finer scale than in the classical setting, where the complexity of a problem is only measured as a function of the number of bits in the input. The first systematic work on parameterized complexity was done by . Under the assumption that P ≠ NP, there exist many natural problems that require superpolynomial running time when complexity is measured in terms of the input size only, but that are computable in a time that is polynomial in the input size and exponential or worse in a parameter . Hence, if is fixed at a small value and the growth of the function over is relatively small then such p ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Fixed-parameter Tractability
In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. The complexity of a problem is then measured as a function of those parameters. This allows the classification of NP-hard problems on a finer scale than in the classical setting, where the complexity of a problem is only measured as a function of the number of bits in the input. The first systematic work on parameterized complexity was done by . Under the assumption that P ≠ NP, there exist many natural problems that require superpolynomial running time when complexity is measured in terms of the input size only, but that are computable in a time that is polynomial in the input size and exponential or worse in a parameter . Hence, if is fixed at a small value and the growth of the function over is relatively small then such p ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Iterative Compression
In computer science, iterative compression is an algorithmic technique for the design of fixed-parameter tractable algorithms, in which one element (such as a vertex of a graph) is added to the problem in each step, and a small solution for the problem prior to the addition is used to help find a small solution to the problem after the step. The technique was invented by Reed, Smith and Vetta. to show that the problem of odd cycle transversal was solvable in time , for a graph with vertices, edges, and odd cycle transversal number . Odd cycle transversal is the problem of finding the smallest set of vertices of a graph that include at least one vertex from every odd cycle; its parameterized complexity was a longstanding open question. . This technique later proved very useful in showing fixed-parameter tractability results. It is now considered to be one of the fundamental techniques in the area of parameterized algorithmics. Iterative compression has been used successfully i ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sunflower Lemma
In the mathematical fields of set theory and extremal combinatorics, a sunflower or \Delta-system is a collection of sets whose pairwise intersection is constant. This constant intersection is called the kernel of the sunflower. The main research question arising in relation to sunflowers is: under what conditions does there exist a ''large'' sunflower (a sunflower with many sets) in a given collection of sets? The \Delta-lemma, sunflower lemma, and the Erdős-Rado sunflower conjecture give successively weaker conditions which would imply the existence of a large sunflower in a given collection, with the latter being one of the most famous open problems of extremal combinatorics. Formal definition Suppose W is a set system over U, that is, a collection of subsets of a set U. The collection W is a ''sunflower'' (or ''\Delta-system'') if there is a subset S of U such that for each distinct A and B in W, we have A \cap B = S. In other words, a set system or collection of set ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Decision Problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whether a given natural number is prime. Another is the problem "given two numbers ''x'' and ''y'', does ''x'' evenly divide ''y''?". The answer is either 'yes' or 'no' depending upon the values of ''x'' and ''y''. A method for solving a decision problem, given in the form of an algorithm, is called a decision procedure for that problem. A decision procedure for the decision problem "given two numbers ''x'' and ''y'', does ''x'' evenly divide ''y''?" would give the steps for determining whether ''x'' evenly divides ''y''. One such algorithm is long division. If the remainder is zero the answer is 'yes', otherwise it is 'no'. A decision problem which can be solved by an algorithm is called ''decidable''. Decision problems typically appear in mat ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Information Processing Letters
''Information Processing Letters'' is a peer reviewed scientific journal in the field of computer science, published by Elsevier Elsevier () is a Dutch academic publishing company specializing in scientific, technical, and medical content. Its products include journals such as ''The Lancet'', ''Cell'', the ScienceDirect collection of electronic journals, '' Trends'', th .... The aim of the journal is to enable fast dissemination of results in the field of information processing in the form of short papers. Submissions are limited to nine double-spaced pages. Both theoretical and experimental research is covered. External links * Computer science journals Publications established in 1971 Semi-monthly journals Elsevier academic journals {{compu-journal-stub ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
SIAM Journal On Computing
The ''SIAM Journal on Computing'' is a scientific journal focusing on the mathematical and formal aspects of computer science. It is published by the Society for Industrial and Applied Mathematics (SIAM). Although its official ISO abbreviation is ''SIAM J. Comput.'', its publisher and contributors frequently use the shorter abbreviation ''SICOMP''. SICOMP typically hosts the special issues of the IEEE Annual Symposium on Foundations of Computer Science (FOCS) and the Annual ACM Symposium on Theory of Computing (STOC), where about 15% of papers published in FOCS and STOC each year are invited to these special issues. For example, Volume 48 contains 11 out of 85 papers published in FOCS 2016. References * External linksSIAM Journal on Computing on |
Journal Of Computer And System Sciences
The ''Journal of Computer and System Sciences'' (JCSS) is a peer-reviewed scientific journal in the field of computer science. ''JCSS'' is published by Elsevier, and it was started in 1967. Many influential scientific articles have been published in ''JCSS''; these include five papers that have won the Gödel Prize. an 2014 Gödel Prize Its managing editor is |
More Examples
More or Mores may refer to: Computing * MORE (application), outline software for Mac OS * more (command), a shell command * MORE protocol, a routing protocol * Missouri Research and Education Network Music Albums * ''More!'' (album), by Booka Shade, 2010 * ''More'' (soundtrack), by Pink Floyd with music from the 1969 film * ''More...'' (Trace Adkins album), or the title song, 1999 * ''More'' (Mary Alessi album), 2005 * ''More'' (Beyoncé EP), 2014 * ''More'' (Michael Bublé EP), 2005 * ''More'' (Clarke-Boland Big Band album), 1968 * ''More'' (Double Dagger album), 2009 * ''More...'' (Montell Jordan album), 1996 * ''More'' (Crystal Lewis album), 2001 * ''More'' (Giuseppi Logan album), 1966 * ''More'' (No Trend album), 2001 * ''More'' (Jeremy Riddle album), or the title song, 2017 * ''More'' (Symphony Number One album), 2016 * ''More'' (Tamia album), or the title song, 2004 * ''More'' (Vitamin C album), 2001 * ''More'', by Mylon LeFevre, 1983 * ''More'', by Resin Dog ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Minor (graph Theory)
Minor may refer to: * Minor (law), a person under the age of certain legal activities. ** A person who has not reached the age of majority * Academic minor, a secondary field of study in undergraduate education Music theory *Minor chord ** Barbershop seventh chord or minor seventh chord *Minor interval *Minor key *Minor scale Mathematics * Minor (graph theory), the relation of one graph to another given certain conditions * Minor (linear algebra), the determinant of a certain submatrix People * Charles Minor (1835–1903), American college administrator * Charles A. Minor (21st-century), Liberian diplomat * Dan Minor (1909–1982), American jazz trombonist * Dave Minor (1922–1998), American basketball player * James T. Minor, US academic administrator and sociologist * Jerry Minor (born 1969), American actor, comedian and writer * Kyle Minor (born 1976), American writer * Mike Minor (actor) (born 1940), American actor * Mike Minor (baseball) (born 1987), American baseball p ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
