|
Baker's Technique
In theoretical computer science, Baker's technique is a method for designing polynomial-time approximation schemes (PTASs) for problems on planar graphs. It is named after Brenda Baker, who announced it in a 1983 conference and published it in the ''Journal of the ACM'' in 1994. The idea for Baker's technique is to break the graph into layers, such that the problem can be solved optimally on each layer, then combine the solutions from each layer in a reasonable way that will result in a feasible solution. This technique has given PTASs for the following problems: subgraph isomorphism, maximum independent set, minimum vertex cover, minimum dominating set, minimum edge dominating set, maximum triangle matching, and many others. The bidimensionality theory of Erik Demaine, Fedor Fomin, Hajiaghayi, and Dimitrios Thilikos and its offshoot ''simplifying decompositions'' (,) generalizes and greatly expands the applicability of Baker's technique for a vast set of problems on planar grap ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Theoretical Computer Science
Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumscribe the theoretical areas precisely. The Association for Computing Machinery, ACM's ACM SIGACT, Special Interest Group on Algorithms and Computation Theory (SIGACT) provides the following description: History While logical inference and mathematical proof had existed previously, in 1931 Kurt Gödel proved with his incompleteness theorem that there are fundamental limitations on what statements could be proved or disproved. Information theory was added to the field with a 1948 mathematical theory of communication by Claude Shannon. In the same decade, Donald Hebb introduced a mathematical model of Hebbian learning, learning in the brain. With mounting biological data supporting this hypothesis with some modification, the fields of n ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Erik Demaine
Erik D. Demaine (born February 28, 1981) is a professor of computer science at the Massachusetts Institute of Technology and a former child prodigy. Early life and education Demaine was born in Halifax, Nova Scotia, to artist sculptor Martin L. Demaine and Judy Anderson. From the age of 7, he was identified as a child prodigy and spent time traveling across North America with his father. He was home-schooled during that time span until entering university at the age of 12. Demaine completed his bachelor's degree at 14 years of age at Dalhousie University in Canada, and completed his PhD at the University of Waterloo by the time he was 20 years old. Demaine's PhD dissertation, a work in the field of computational origami, was completed at the University of Waterloo under the supervision of Anna Lubiw and Ian Munro. This work was awarded the Canadian Governor General's Gold Medal from the University of Waterloo and the NSERC Doctoral Prize (2003) for the best PhD thesis an ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
1983 In Computing
The year 1983 saw both the official beginning of the Internet and the first mobile cellular telephone call. Events January * January 1 – The migration of the ARPANET to Internet protocol suite, TCP/IP is officially completed (this is considered to be the beginning of the true Internet). * January 24 – Twenty-five members of the Red Brigades are sentenced to life imprisonment for the 1978 murder of Italian politician Aldo Moro. * January 25 ** High-ranking Nazism, Nazi war crime, war criminal Klaus Barbie is arrested in Bolivia. ** IRAS is launched from Vandenberg AFB, to conduct the world's first all-sky infrared survey from space. February * February 2 – Giovanni Vigliotto goes on trial on charges of polygamy involving 105 women. * February 3 – Prime Minister of Australia Malcolm Fraser is granted a double dissolution of both houses of parliament, for 1983 Australian federal election, elections on March 5, 1983. As Fraser is being granted the dissolution, Bill Hayden ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
K-outerplanar Graph
In graph theory, a ''k''-outerplanar graph is a planar graph that has a planar embedding in which the vertices belong to at most k concentric layers. The outerplanarity index of a planar graph is the minimum value of k for which it is k-outerplanar. Definition An outerplanar graph (or 1-outerplanar graph) has all of its vertices on the unbounded (outside) face of the graph. A 2-outerplanar graph is a planar graph with the property that, when the vertices on the unbounded face are removed, the remaining vertices all lie on the newly formed unbounded face. And so on. More formally, a graph is k-outerplanar if it has a planar embedding such that, for every vertex, there is an alternating sequence of at most k faces and k vertices of the embedding, starting with the unbounded face and ending with the vertex, in which each consecutive face and vertex are incident to each other. Properties and applications The k-outerplanar graphs have treewidth at most 3k-1. However, some bounded-tree ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Dynamic Programming
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. In both contexts it refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner. While some decision problems cannot be taken apart this way, decisions that span several points in time do often break apart recursively. Likewise, in computer science, if a problem can be solved optimally by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems, then it is said to have ''optimal substructure''. If sub-problems can be nested recursively inside larger problems, so that dynamic programming methods are applicable, then there is a relation between the value of the larger problem and the values of the sub-problems.Cormen, T. H.; Leiserson, C. E.; Rives ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Independent Set (graph Theory)
In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set S of vertices such that for every two vertices in S, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in S. A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening. A maximal independent set is an independent set that is not a proper subset of any other independent set. A maximum independent set is an independent set of largest possible size for a given graph G. This size is called the independence number of ''G'' and is usually denoted by \alpha(G). The optimization problem of finding such a set is called the maximum independent set problem. It is a strongly NP-hard problem. As such ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
1-planar Graph
In topological graph theory, a 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point, where it crosses a single additional edge. If a 1-planar graph, one of the most natural generalizations of planar graphs, is drawn that way, the drawing is called a 1-plane graph or 1-planar embedding of the graph. Coloring 1-planar graphs were first studied by , who showed that they can be colored with at most seven colors. Later, the precise number of colors needed to color these graphs, in the worst case, was shown to be six.. The example of the complete graph ''K''6, which is 1-planar, shows that 1-planar graphs may sometimes require six colors. However, the proof that six colors are always enough is more complicated. Ringel's motivation was in trying to solve a variation of total coloring for planar graphs, in which one simultaneously colors the vertices and faces of a planar graph in such a way that no two adjacent ve ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Minor
In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges and vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if its minors include neither the complete graph nor the complete bipartite graph ., p. 77; . The Robertson–Seymour theorem implies that an analogous forbidden minor characterization exists for every property of graphs that is preserved by deletions and edge contractions., theorem 4, p. 78; . For every fixed graph , it is possible to test whether is a minor of an input graph in polynomial time; together with the forbidden minor characterization this implies that every graph property preserved by deletions and contractions may be recognized in polynomial time. Other results and conjectures involving graph minors include the graph structure theorem, according to which the graphs that do not have as a minor may be formed by glui ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mohammad Hajiaghayi
, birth_date = , birth_place = , death_place = , nationality = , fields = Computer science , workplaces = University of Maryland, College Park , alma_mater = Massachusetts Institute of Technology (PhD) , doctoral_advisor = Erik Demaine F. Thomson Leighton , doctoral_students = , awards = Guggenheim Fellowship (2019) Blavatnik National Awards for Young Scientists (2020) EATCS Fellow (2020) IEEE Fellow (2019) ACM Fellow (2018) EATCS Nerode Prize (2015) , website = Mohammad Taghi Hajiaghayi ( fa, محمد تقی حاجی آقائی) is a computer scientist known for his work in algorithms, game theory, social networks, network design, graph theory, and big data.. He has over 200 publications with over 185 collaborators and 10 issued patents. He is the Jack and Rita G. Minker Professor at the University of Maryland Department of Computer Science. Professional career Hajiaghayi received his PhD in applie ... [...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] |
Polynomial-time Approximation Scheme
In computer science (particularly algorithmics), a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems). A PTAS is an algorithm which takes an instance of an optimization problem and a parameter and produces a solution that is within a factor of being optimal (or for maximization problems). For example, for the Euclidean traveling salesman problem, a PTAS would produce a tour with length at most , with being the length of the shortest tour. The running time of a PTAS is required to be polynomial in the problem size for every fixed ε, but can be different for different ε. Thus an algorithm running in time or even counts as a PTAS. Variants Deterministic A practical problem with PTAS algorithms is that the exponent of the polynomial could increase dramatically as ε shrinks, for example if the runtime is . One way of addressing this is to define the efficient polynomial-time a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Edge Dominating Set
In graph theory, an edge dominating set for a graph ''G'' = (''V'', ''E'') is a subset ''D'' ⊆ ''E'' such that every edge not in ''D'' is adjacent to at least one edge in ''D''. An edge dominating set is also known as a ''line dominating set''. Figures (a)–(d) are examples of edge dominating sets (thick red lines). A minimum edge dominating set is a smallest edge dominating set. Figures (a) and (b) are examples of minimum edge dominating sets (it can be checked that there is no edge dominating set of size 2 for this graph). Properties An edge dominating set for ''G'' is a dominating set for its line graph ''L''(''G'') and vice versa. Any maximal matching is always an edge dominating set. Figures (b) and (d) are examples of maximal matchings. Furthermore, the size of a minimum edge dominating set equals the size of a minimum maximal matching. A minimum maximal matching is a minimum edge dominating set; Figure (b) is an example of a minimum maxim ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
