Draft:Paull-Unger Algorithm
| Submission declined on 23 August 2024 by Utopes (talk). This submission does not appear to be written in the formal tone expected of an encyclopedia article. Entries should be written from a neutral point of view, and should refer to a range of independent, reliable, published sources. Please rewrite your submission in a more encyclopedic format. Please make sure to avoid peacock terms that promote the subject.
Where to get help
How to improve a draft
You can also browse Wikipedia:Featured articles and Wikipedia:Good articles to find examples of Wikipedia's best writing on topics similar to your proposed article. Improving your odds of a speedy review To improve your odds of a faster review, tag your draft with relevant WikiProject tags using the button below. This will let reviewers know a new draft has been submitted in their area of interest. For instance, if you wrote about a female astronomer, you would want to add the Biography, Astronomy, and Women scientists tags. Editor resources
|  |
Comment: Avoid using WP:PEACOCK words, especially when there's no citations to be add when they are mentioned (i.e. "vital role", "powerful assets", "theorem's utility continues to expand"). All of these are unreferenced and don't pass WP:NPOV anyway as is. Utopes (talk / cont) 22:01, 23 August 2024 (UTC)
The Paull-Unger Theorem, developed by Marvin C. Paull and H. Unger[1], is a crucial theoretical framework in the field of automata theory, particularly for the minimization of incomplete machines and the identification of maximal independent sets (MIS). This theorem plays a vital role in reducing the number of states in sequential circuits, which is essential for optimizing the efficiency of computational systems.
Graph Theory and the Independent Set Problem
[edit]In the realm of graph theory, the Paull-Unger Theorem is instrumental in addressing the independent set problem, a common challenge where one seeks to find the largest group of nodes within a graph that are not directly connected by edges. These groups, known as independent sets, are crucial for various applications, from network design to resource allocation.
The Paull-Unger Algorithm is specifically designed to identify all maximal independent sets within a graph. Furthermore, it calculates the graph's independence number—the size of the largest independent set. This algorithm is particularly effective for solving complex network problems, making it a valuable tool in network analysis and optimization.[2]
Paull-Unger Algorithm's pseudo code is[1]
β, i, j, n: positive integers
E: array of size (n+ × n+) containing elements of B
L, M: subsets of B*
v: array of size B containing elements of V
x: element of B*
σ: element of B*
- begin
- T ← ∅;
- T[ε] ← V;
- L ← {ε};
- for j ← 1 to n – 1 do
- for i ← j + 1 to n do
- if E[i, j] = 1 then
- begin
- M ← {x ∈ L: {vi, vj} ⊆ T[x]};
- L ← L \ M;
- v[0] ← vi;
- v[1] ← vj;
- for x ∈ M do
- for σ ∈ B do
- begin
- T[xσ] ← T[x] \ {v[σ]};
- if (T[xσ] ⇒ T[y] for all y ∈ L) then
- L ← L ∪ {xσ};
- end;
- end;
- β ← max{|T[x]| for all x ∈ L};
- end;
Conclusion
[edit]The Paull-Unger Theorem and its associated algorithm are powerful assets in both theoretical and applied mathematics. Their ability to efficiently minimize states in incomplete machines and solve complex graph theory problems underscores their importance in a variety of fields, from automata theory to GIS. With the advent of interactive tools that facilitate learning and application, the theorem's utility continues to expand, offering new opportunities for innovation in complex problem-solving.
- in-depth (not just passing mentions about the subject)
- reliable
- secondary
- independent of the subject
Make sure you add references that meet these criteria before resubmitting. Learn about mistakes to avoid when addressing this issue. If no additional references exist, the subject is not suitable for Wikipedia.