|
Pebble Motion Problems
The pebble motion problems, or pebble motion on graphs, are a set of related problems in graph theory dealing with the movement of multiple objects ("pebbles") from vertex to vertex in a graph with a constraint on the number of pebbles that can occupy a vertex at any time. Pebble motion problems occur in domains such as multi-robot motion planning (in which the pebbles are robots) and network routing (in which the pebbles are packets of data). The best-known example of a pebble motion problem is the famous 15 puzzle where a disordered group of fifteen tiles must be rearranged within a 4x4 grid by sliding one tile at a time. Theoretical formulation The general form of the pebble motion problem is Pebble Motion on Graphs formulated as follows: Let G = (V,E) be a graph with n vertices. Let P = \ be a set of pebbles with k < n. An arrangement of pebbles is a mapping such that for . A move |
Graph Theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph theory), vertices'' (also called ''nodes'' or ''points'') which are connected by ''Glossary of graph theory terms#edge, edges'' (also called ''arcs'', ''links'' or ''lines''). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics. Definitions Definitions in graph theory vary. The following are some of the more basic ways of defining graphs and related mathematical structures. Graph In one restricted but very common sense of the term, a graph is an ordered pair G=(V,E) comprising: * V, a Set (mathematics), set of vertices (also called nodes or points); * ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph (discrete Mathematics)
In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a Set (mathematics), set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called ''Vertex (graph theory), vertices'' (also called ''nodes'' or ''points'') and each of the related pairs of vertices is called an ''edge'' (also called ''link'' or ''line''). Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. The edges may be directed or undirected. For example, if the vertices represent people at a party, and there is an edge between two people if they shake hands, then this graph is undirected because any person ''A'' can shake hands with a person ''B'' only if ''B'' also shakes hands with ''A''. In contrast, if an edge from a person ''A'' to a person ''B'' means that ''A'' owes money to ''B'', then this graph is directed, because owing mon ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Robot
A robot is a machine—especially one Computer program, programmable by a computer—capable of carrying out a complex series of actions Automation, automatically. A robot can be guided by an external control device, or the robot control, control may be embedded within. Robots may be constructed to evoke Humanoid robot, human form, but most robots are task-performing machines, designed with an emphasis on stark functionality, rather than expressive aesthetics. Robots can be autonomous robot, autonomous or semi-autonomous and range from humanoids such as Honda's ''Advanced Step in Innovative Mobility'' (ASIMO) and TOSY's ''TOSY Ping Pong Playing Robot'' (TOPIO) to industrial robots, robot-assisted surgery, medical operating robots, patient assist robots, dog therapy robots, collectively programmed Swarm robotics, ''swarm'' robots, UAV drones such as General Atomics MQ-1 Predator, and even microscopic Nanorobotics, nanorobots. By mimicking a lifelike appearance or automating mo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Motion Planning
Motion planning, also path planning (also known as the navigation problem or the piano mover's problem) is a computational problem to find a sequence of valid configurations that moves the object from the source to destination. The term is used in computational geometry, computer animation, robotics and computer games. For example, consider navigating a mobile robot inside a building to a distant waypoint. It should execute this task while avoiding walls and not falling down stairs. A motion planning algorithm would take a description of these tasks as input, and produce the speed and turning commands sent to the robot's wheels. Motion planning algorithms might address robots with a larger number of joints (e.g., industrial manipulators), more complex tasks (e.g. manipulation of objects), different constraints (e.g., a car that can only drive forward), and uncertainty (e.g. imperfect models of the environment or robot). Motion planning has several robotics applications, such ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Network Routing
Routing is the process of selecting a path for traffic in a network or between or across multiple networks. Broadly, routing is performed in many types of networks, including circuit-switched networks, such as the public switched telephone network (PSTN), and computer networks, such as the Internet. In packet switching networks, routing is the higher-level decision making that directs network packets from their source toward their destination through intermediate network nodes by specific packet forwarding mechanisms. Packet forwarding is the transit of network packets from one network interface to another. Intermediate nodes are typically network hardware devices such as routers, gateways, firewalls, or switches. General-purpose computers also forward packets and perform routing, although they have no specially optimized hardware for the task. The routing process usually directs forwarding on the basis of routing tables. Routing tables maintain a record of the routes to ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Data Packet
In telecommunications and computer networking, a network packet is a formatted unit of data carried by a packet-switched network. A packet consists of control information and user data; the latter is also known as the '' payload''. Control information provides data for delivering the payload (e.g., source and destination network addresses, error detection codes, or sequencing information). Typically, control information is found in packet headers and trailers. In packet switching, the bandwidth of the transmission medium is shared between multiple communication sessions, in contrast to circuit switching, in which circuits are preallocated for the duration of one session and data is typically transmitted as a continuous bit stream. Terminology In the seven-layer OSI model of computer networking, ''packet'' strictly refers to a protocol data unit at layer 3, the network layer. A data unit at layer 2, the data link layer, is a '' frame''. In layer 4, the transport layer, the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
15 Puzzle
The 15 puzzle (also called Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square and more) is a sliding puzzle. It has 15 square tiles numbered 1 to 15 in a frame that is 4 tile positions high and 4 tile positions wide, with one unoccupied position. Tiles in the same row or column of the open position can be moved by sliding them horizontally or vertically, respectively. The goal of the puzzle is to place the tiles in numerical order (from left to right, top to bottom). Named after the number of tiles in the frame, the 15 puzzle may also be called a ''"16 puzzle"'', alluding to its total tile capacity. Similar names are used for different sized variants of the 15 puzzle, such as the 8 puzzle, which has 8 tiles in a 3×3 frame. The ''n'' puzzle is a classical problem for modeling algorithms involving heuristics. Commonly used heuristics for this problem include counting the number of misplaced tiles and finding the sum of the taxicab distances between each block and its posit ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Tree Graph
In graph theory, a tree is an undirected graph in which any two vertices are connected by path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by path, or equivalently an acyclic undirected graph, or equivalently a disjoint union of trees. A directed tree, oriented tree,See .See . polytree,See . or singly connected networkSee . is a directed acyclic graph (DAG) whose underlying undirected graph is a tree. A polyforest (or directed forest or oriented forest) is a directed acyclic graph whose underlying undirected graph is a forest. The various kinds of data structures referred to as trees in computer science have underlying graphs that are trees in graph theory, although such data structures are generally rooted trees. A rooted tree may be directed, called a directed rooted tree, either making all its edges point away from the root—in which case it is called an arborescence or out-tree—or ma ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lattice Graph
In graph theory, a lattice graph, mesh graph, or grid graph is a graph whose drawing, embedded in some Euclidean space , forms a regular tiling. This implies that the group of bijective transformations that send the graph to itself is a lattice in the group-theoretical sense. Typically, no clear distinction is made between such a graph in the more abstract sense of graph theory, and its drawing in space (often the plane or 3D space). This type of graph may more shortly be called just a lattice, mesh, or grid. Moreover, these terms are also commonly used for a finite section of the infinite graph, as in "an 8 × 8 square grid". The term lattice graph has also been given in the literature to various other kinds of graphs with some regular structure, such as the Cartesian product of a number of complete graphs. Square grid graph A common type of lattice graph (known under different names, such as grid graph or square grid graph) is the graph whose vertices corresp ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Biconnected Graph
In graph theory, a biconnected graph is a connected and "nonseparable" graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ..., meaning that if any one vertex were to be removed, the graph will remain connected. Therefore a biconnected graph has no articulation vertices. The property of being k-vertex-connected graph, 2-connected is equivalent to biconnectivity, except that the complete graph of two vertices is usually not regarded as 2-connected. This property is especially useful in maintaining a graph with a two-fold Redundancy (engineering), redundancy, to prevent disconnection upon the removal of a single edge (graph theory), edge (or connection). The use of biconnected graphs is very important in the field of networking (see Flow network, Network flow), because of this pr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
NP Hard
NP may refer to: Arts and entertainment * NP (novel), ''NP'' (novel), by Japanese author Banana Yoshimoto Organizations * Nashua-Plainfield Community School District, Iowa, United States * National Party (other), various political parties * Ngee Ann Polytechnic, Singapore * Nigeria Police Force * Northern Pacific Railway (AAR reporting mark NP) * November Project, free, open-to-the-public exercise group Places * NP postcode area, Newport, Wales, UK * Nepal (ISO 3166-1 alpha-2 country code NP) ** .np, the country code top level domain (ccTLD) for Nepal Science, technology and mathematics Biology and medicine * Nucleoside phosphorylase, an enzyme * Nurse practitioner * Kallikrein 8, an enzyme * Neptunium, symbol Np, a chemical element * Nosocomial pneumonia * Natriuretic peptide Mathematics and computer science * NP (complexity), Nondeterministic Polynomial, a computational complexity class ** NP-complete, a class of decision problems ** NP-hard, a class of problems in c ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
SIAM Journal On Discrete Mathematics
'' SIAM Journal on Discrete Mathematics'' is a peer-reviewed mathematics journal published quarterly by the Society for Industrial and Applied Mathematics (SIAM). The journal includes articles on pure and applied discrete mathematics. It was established in 1988, along with the ''SIAM Journal on Matrix Analysis and Applications'', to replace the '' SIAM Journal on Algebraic and Discrete Methods''. The journal is indexed by ''Mathematical Reviews'' and Zentralblatt MATH. Its 2009 MCQ was 0.57. According to the ''Journal Citation Reports'', the journal has a 2016 impact factor of 0.755. Although its official ISO abbreviation is ''SIAM J. Discrete Math.'', its publisher and contributors frequently use the shorter abbreviation ''SIDMA''. References External links * Discrete mathematics journals Academic journals established in 1988 English-language journals Discrete Mathematics Discrete mathematics is the study of mathematical structures that can be considered "discre ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
