Related Research Articles
In Boolean logic, the majority function is the Boolean function that evaluates to false when half or more arguments are false and true otherwise, i.e. the value of the function equals the value of the majority of the inputs. Representing true values as 1 and false values as 0, we may use the (real-valued) formula:
Dagstuhl is a computer science research center in Germany, located in and named after a district of the town of Wadern, Merzig-Wadern, Saarland.
In graph theory, the metric dimension of a graph G is the minimum cardinality of a subset S of vertices such that all other vertices are uniquely determined by their distances to the vertices in S. Finding the metric dimension of a graph is an NP-hard problem; the decision version, determining whether the metric dimension is less than a given value, is NP-complete.
In computational complexity theory, a nonelementary problem is a problem that is not a member of the class ELEMENTARY. As a class it is sometimes denoted as NONELEMENTARY.
Russell Graham Impagliazzo is a professor of computer science at the University of California, San Diego, specializing in computational complexity theory.
In graph theory, the Laman graphs are a family of sparse graphs describing the minimally rigid systems of rods and joints in the plane. Formally, a Laman graph is a graph on n vertices such that, for all k, every k-vertex subgraph has at most 2k − 3 edges, and such that the whole graph has exactly 2n − 3 edges. Laman graphs are named after Gerard Laman, of the University of Amsterdam, who in 1970 used them to characterize rigid planar structures. This characterization, however, had already been discovered in 1927 by Hilda Geiringer.
In computational geometry, a bitonic tour of a set of point sites in the Euclidean plane is a closed polygonal chain that has each site as one of its vertices, such that any vertical line crosses the chain at most twice.
Ever since Sir William Thomson's vortex theory, mathematicians have tried to classify and tabulate all possible knots. As of May 2008, all prime knots up to 16 crossings have been tabulated. The major challenge of the process is that many apparently different knots may actually be different geometrical presentations of the same topological entity, and that proving or disproving knot equivalence is much more difficult than it at first seems.
WADS, the Algorithms and Data Structures Symposium, is an international academic conference in the field of computer science, focusing on algorithms and data structures. WADS is held every second year, usually in Canada and always in North America. It is held in alternation with its sister conference, the Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), which is usually held in Scandinavia and always in Northern Europe. Historically, the proceedings of both conferences were published by Springer Verlag through their Lecture Notes in Computer Science series. Springer continues to publish WADS proceedings, but starting in 2016, SWAT proceedings are now published by Dagstuhl through their Leibniz International Proceedings in Informatics.
Susanne Boll is a Professor for Media Informatics and Multimedia Systems in the Department of Computing Science at the University of Oldenburg, Germany. Boll is a member of SIGMM of the ACM and is a member of the board at the research institute OFFIS. She founded and directs the HCI Lab at the University of Oldenburg and OFFIS.
In computer science, the method of contraction hierarchies is a speed-up technique for finding the shortest-path in a graph. The most intuitive applications are car-navigation systems: a user wants to drive from to using the quickest possible route. The metric optimized here is the travel time. Intersections are represented by vertices, the road sections connecting them by edges. The edge weights represent the time it takes to drive along this segment of the road. A path from to is a sequence of edges ; the shortest path is the one with the minimal sum of edge weights among all possible paths. The shortest path in a graph can be computed using Dijkstra's algorithm but, given that road networks consist of tens of millions of vertices, this is impractical. Contraction hierarchies is a speed-up method optimized to exploit properties of graphs representing road networks. The speed-up is achieved by creating shortcuts in a preprocessing phase which are then used during a shortest-path query to skip over "unimportant" vertices. This is based on the observation that road networks are highly hierarchical. Some intersections, for example highway junctions, are "more important" and higher up in the hierarchy than for example a junction leading into a dead end. Shortcuts can be used to save the precomputed distance between two important junctions such that the algorithm doesn't have to consider the full path between these junctions at query time. Contraction hierarchies do not know about which roads humans consider "important", but they are provided with the graph as input and are able to assign importance to vertices using heuristics.
In the design of algorithms, partition refinement is a technique for representing a partition of a set as a data structure that allows the partition to be refined by splitting its sets into a larger number of smaller sets. In that sense it is dual to the union-find data structure, which also maintains a partition into disjoint sets but in which the operations merge pairs of sets. In some applications of partition refinement, such as lexicographic breadth-first search, the data structure maintains as well an ordering on the sets in the partition.
Dorothea Wagner is a German computer scientist, known for her research in graph drawing, route planning, and social network analysis. She heads the Institute of Theoretical Informatics at the Karlsruhe Institute of Technology.
Multitier programming is a programming paradigm for distributed software, which typically follows a multitier architecture, physically separating different functional aspects of the software into different tiers. Multitier programming allows functionalities that span multiple of such tiers to be developed in a single compilation unit using a single programming language. Without multitier programming, tiers are developed using different languages, e.g., JavaScript for the Web client, PHP for the Web server and SQL for the database. Multitier programming is often integrated into general-purpose languages by extending them with support for distribution.
The International Symposium on Experimental Algorithms (SEA), previously known as Workshop on Experimental Algorithms (WEA), is a computer science conference in the area of algorithm engineering.
Cognitive discourse analysis (CODA) is a research method which examines natural language data in order to gain insights into patterns in (verbalisable) thought. The term was coined by Thora Tenbrink to describe a kind of discourse analysis that had been carried out by researchers in linguistics and other fields. As it is limited to examining verbalisable thought, CODA studies are often triangulated against other research methods. The method is theoretically neutral, and can therefore be used alongside a range of different models of cognition and grammar.
In computer science, choreographic programming is a programming paradigm where programs are compositions of interactions among multiple concurrent participants.
The twin-width of an undirected graph is a natural number associated with the graph, used to study the parameterized complexity of graph algorithms. Intuitively, it measures how similar the graph is to a cograph, a type of graph that can be reduced to a single vertex by repeatedly merging together twins, vertices that have the same neighbors. The twin-width is defined from a sequence of repeated mergers where the vertices are not required to be twins, but have nearly equal sets of neighbors.
A parameterized approximation algorithm is a type of algorithm that aims to find approximate solutions to NP-hard optimization problems in polynomial time in the input size and a function of a specific parameter. These algorithms are designed to combine the best aspects of both traditional approximation algorithms and fixed-parameter tractability.
References
- ↑ "Algorithms – ESA 2012 (Lecture Notes in Computer Science)" (PDF). 2012. Retrieved 2012-09-17.[ dead link ]
- ↑ "Test-of-Time Award – ESA" . Retrieved 2023-08-29.
- ↑ "Schedule – ALGO 2022" . Retrieved 2023-08-29.
- ↑ "ALGO 2020 - September 7-10, 2020 - Pisa, Italy". algo2020.di.unipi.it. Retrieved 2023-08-29.
- ↑ "ESA 2018: Program". algo2018.hiit.fi. Retrieved 2023-08-29.
- ↑ Pruhs, Kirk; Sohler, Christian (2017). Pruhs, Kirk; Sohler, Christian (eds.). "Front Matter, Table of Contents, Preface, Programm Commitees, External Reviewers". 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. 87: 0:i–0:xx. doi:10.4230/LIPIcs.ESA.2017.0. ISBN 978-3-95977-049-1.
- ↑ Sankowski, Piotr; Zaroliagis, Christos (2016). Sankowski, Piotr; Zaroliagis, Christos (eds.). "Front Matter, Table of Contents, Preface, Programm Commitee, External Reviewers". 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. 57: 0:i–0:xxiv. doi:10.4230/LIPIcs.ESA.2016.0. ISBN 978-3-95977-015-6.
