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.
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 mathematics, a graph partition is the reduction of a graph to a smaller graph by partitioning its set of nodes into mutually exclusive groups. Edges of the original graph that cross between the groups will produce edges in the partitioned graph. If the number of resulting edges is small compared to the original graph, then the partitioned graph may be better suited for analysis and problem-solving than the original. Finding a partition that simplifies graph analysis is a hard problem, but one that has applications to scientific computing, VLSI circuit design, and task scheduling in multiprocessor computers, among others. Recently, the graph partition problem has gained importance due to its application for clustering and detection of cliques in social, pathological and biological networks. For a survey on recent trends in computational methods and applications see Buluc et al. (2013). Two common examples of graph partitioning are minimum cut and maximum cut problems.
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. However, this characterization, the Geiringer–Laman theorem, 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. and is a member of the board at the research institute OFFIS. She is a member of SIGMM and SIGCHI of the ACM as well as the German Informatics Society GI. She founded and directs the HCI Lab at the University of Oldenburg and OFFIS.
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.
Christopher Umans is a professor of Computer Science in the Computing and Mathematical Sciences Department at the California Institute of Technology. He is known for work on algorithms, computational complexity, algebraic complexity, and hardness of approximation.
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.
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.
The highway dimension is a graph parameter modelling transportation networks, such as road networks or public transportation networks. It was first formally defined by Abraham et al. based on the observation by Bast et al. that any road network has a sparse set of "transit nodes", such that driving from a point A to a sufficiently far away point B along the shortest route will always pass through one of these transit nodes. It has also been proposed that the highway dimension captures the properties of public transportation networks well, given that longer routes using busses, trains, or airplanes will typically be serviced by larger transit hubs. This relates to the spoke–hub distribution paradigm in transport topology optimization.
Melanie Schmidt is a German computer scientist whose research involves algorithms for cluster analysis, including approximation algorithms, coresets, algorithmic fairness, and inapproximability. She holds the chair for Algorithms and Data Structures in the Computer Science Department at Heinrich Heine University Düsseldorf.
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 Committees, External Reviewers". 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs). 87. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 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 Committee, External Reviewers". 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs). 57. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 0:i–0:xxiv. doi: 10.4230/LIPIcs.ESA.2016.0 . ISBN 978-3-95977-015-6.
