|
Bipartite Realization Problem
The bipartite realization problem is a classical decision problem in graph theory, a branch of combinatorics. Given two finite sequences (a_1,\dots,a_n) and (b_1,\dots,b_n) of natural numbers, the problem asks whether there is a labeled simple bipartite graph such that (a_1,\dots,a_n),(b_1,\dots,b_n) is the degree sequence of this bipartite graph. Solutions The problem belongs to the complexity class P. This can be proven using the Gale–Ryser theorem, i.e., one has to validate the correctness of n inequalities. Other notations The problem can also be stated in terms of zero-one matrices Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** ''The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis .... The connection can be seen if one realizes that each bipartite graph has a Adjacency matrix of a bipartite graph, biadjacency matrix where the ... [...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] |
Graph Realization Problem
The graph realization problem is a decision problem in graph theory. Given a finite sequence (d_1,\dots,d_n) of natural numbers, the problem asks whether there is a labeled simple graph such that (d_1,\dots,d_n) is the degree sequence of this graph. Solutions The problem can be solved in polynomial time. One method of showing this uses the Havel–Hakimi algorithm constructing a special solution with the use of a recursive algorithm. Alternatively, following the characterization given by the Erdős–Gallai theorem, the problem can be solved by testing the validity of n inequalities. Other notations The problem can also be stated in terms of symmetric matrices of zeros and ones. The connection can be seen if one realizes that each graph has an adjacency matrix where the column sums and row sums correspond to (d_1,\ldots,d_n). The problem is then sometimes denoted by ''symmetric 0-1-matrices for given row sums''. Related problems Similar problems describe the degree sequences of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
John Wiley & Sons
John Wiley & Sons, Inc., commonly known as Wiley (), is an American multinational publishing company founded in 1807 that focuses on academic publishing and instructional materials. The company produces books, journals, and encyclopedias, in print and electronically, as well as online products and services, training materials, and educational materials for undergraduate, graduate, and continuing education students. History The company was established in 1807 when Charles Wiley opened a print shop in Manhattan. The company was the publisher of 19th century American literary figures like James Fenimore Cooper, Washington Irving, Herman Melville, and Edgar Allan Poe, as well as of legal, religious, and other non-fiction titles. The firm took its current name in 1865. Wiley later shifted its focus to scientific, technical, and engineering subject areas, abandoning its literary interests. Wiley's son John (born in Flatbush, New York, October 4, 1808; died in East Orange, New Je ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Factorization
In graph theory, a factor of a graph ''G'' is a spanning subgraph, i.e., a subgraph that has the same vertex set as ''G''. A ''k''-factor of a graph is a spanning ''k''- regular subgraph, and a ''k''-factorization partitions the edges of the graph into disjoint ''k''-factors. A graph ''G'' is said to be ''k''-factorable if it admits a ''k''-factorization. In particular, a 1-factor is a perfect matching, and a 1-factorization of a ''k''-regular graph is an edge coloring with ''k'' colors. A 2-factor is a collection of cycles that spans all vertices of the graph. 1-factorization If a graph is 1-factorable (ie, has a 1-factorization), then it has to be a regular graph. However, not all regular graphs are 1-factorable. A ''k''-regular graph is 1-factorable if it has chromatic index ''k''; examples of such graphs include: * Any regular bipartite graph. Hall's marriage theorem can be used to show that a ''k''-regular bipartite graph contains a perfect matching. One can then remove t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Catherine Greenhill
Catherine Greenhill is an Australian mathematician known for her research on random graphs, combinatorial enumeration and Markov chains. She is a professor of mathematics in the School of Mathematics and Statistics at the University of New South Wales, and an editor-in-chief of the ''Electronic Journal of Combinatorics''. Education and career Greenhill did her undergraduate studies at the University of Queensland, and remained there for a master's degree, working with Anne Penfold Street there. She earned her Ph.D. in 1996 at the University of Oxford, under the supervision of Peter M. Neumann. Her dissertation was ''From Multisets to Matrix Groups: Some Algorithms Related to the Exterior Square''. After postdoctoral research with Martin Dyer at the University of Leeds and Nick Wormald at the University of Melbourne, Greenhill joined the University of New South Wales in 2003. She was promoted to associate professor in 2014, becoming the first female mathematician to earn such ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sequence (graph Theory)
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called the ''length'' of the sequence. Unlike a set, the same elements can appear multiple times at different positions in a sequence, and unlike a set, the order does matter. Formally, a sequence can be defined as a function from natural numbers (the positions of elements in the sequence) to the elements at each position. The notion of a sequence can be generalized to an indexed family, defined as a function from an ''arbitrary'' index set. For example, (M, A, R, Y) is a sequence of letters with the letter 'M' first and 'Y' last. This sequence differs from (A, R, M, Y). Also, the sequence (1, 1, 2, 3, 5, 8), which contains the number 1 at two different positions, is a valid sequence. Sequences can be '' finite'', as in these examples, or '' in ... [...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] |
Complete Bipartite Graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory itself is typically dated as beginning with Leonhard Euler's 1736 work on the Seven Bridges of Königsberg. However, drawings of complete bipartite graphs were already printed as early as 1669, in connection with an edition of the works of Ramon Llull edited by Athanasius Kircher. Llull himself had made similar drawings of complete graphs three centuries earlier.. Definition A complete bipartite graph is a graph whose vertices can be partitioned into two subsets and such that no edge has both endpoints in the same subset, and every possible edge that could connect vertices in different subsets is part of the graph. That is, it is a bipartite graph such that for every two vertices and, is an edge in . A complete bipartite graph w ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Digraph Realization Problem
The digraph realization problem is a decision problem in graph theory. Given pairs of nonnegative integers ((a_1,b_1),\ldots,(a_n,b_n)), the problem asks whether there is a labeled simple directed graph such that each vertex v_i has indegree a_i and outdegree b_i. Solutions The problem belongs to the complexity class P. Two algorithms are known to prove that. The first approach is given by the Kleitman–Wang algorithms constructing a special solution with the use of a recursive algorithm. The second one is a characterization by the Fulkerson–Chen–Anstee theorem, i.e. one has to validate the correctness of n inequalities. Other Notations The problem can also be stated in terms of zero-one matrices. The connection can be seen if one realizes that each directed graph has an adjacency matrix where the column sums and row sums correspond to (a_1,\cdots,a_n) and (b_1,\ldots,b_n). Note that the diagonal of the matrix only contains zeros. The problem is then often denoted by ''0-1-m ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph (discrete Mathematics)
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a Set (mathematics), set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical 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. Graphs are one of the objects of study in discrete mathematics. 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'' m ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are connected by '' edges'' (also called ''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 of vertices (also called nodes or points); * E \subseteq \, a set of edges (also called links or lines), which are unordered pairs of vertices (that is, an edge is associated with t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
