Bipartite dimension and Wikipedia:Featured list candidates/backlog/items: Difference between pages

Content deleted Content added

VisualWikitext

Inline

Revision as of 21:53, 10 October 2008

Template:Multicol

Template:Multicol-break

Template:Multicol-end

@@ Line 1: / Line 1: @@
+<!-- THIS LIST IS ORDERED FROM MOST URGENT TO LEAST URGENT, FROM TOP TO BOTTOM -->
-In the mathematical field of [[graph theory]], the '''bipartite dimension''' of an [[graph]] G=(V,E) is the minimum number of [[biclique]]s, that is, complete bipartite subgraphs, needed to [[covering (graph theory)|cover]] all edges in E. A collection of bicliques covering all edges in G is called a '''biclique edge cover''', or sometimes '''biclique cover'''. The bipartite dimension of G is often denoted by the symbol d(G).
+{{multicol}}
+* [[Wikipedia:Featured list candidates/List of Bleach episodes (season 8)|List of Bleach episodes (season 8)]]
-==Bipartite dimension of some special graphs==
+* [[Wikipedia:Featured list candidates/The O.C. (season 3)|The O.C. (season 3)]]
-Fishburn and Hammer determine the bipartite dimension for some special graphs. For example, the path <math>P_n</math>
+* [[Wikipedia:Featured list candidates/List of Bleach episodes (season 5)|List of Bleach episodes (season 5)]]
-has <math>d(P_n) = \lfloor n/2 \rfloor</math>, the cycle <math>C_n</math> has <math>d(C_n)=\lceil n/2\rceil</math>,
+* [[Wikipedia:Featured list candidates/List of universities in Ontario|List of universities in Ontario]]
-and the complete graph <math>K_n</math> has <math>d(K_n) = \lceil\log n \rceil</math>.
+* [[Wikipedia:Featured list candidates/List of awards and nominations received by The White Stripes|List of awards and nominations received by The White Stripes]]
+* [[Wikipedia:Featured list candidates/Timeline of the 2006 Pacific hurricane season|Timeline of the 2006 Pacific hurricane season]]
-==Computational complexity==
+* [[Wikipedia:Featured list candidates/List of number-one Billboard Top Latin Albums of 2003|List of number-one Billboard Top Latin Albums of 2003]]
-Determining d(G) is an [[optimization problem]]. The [[decision problem]] for bipartite dimension can be phrased as:
+* [[Wikipedia:Featured list candidates/List of Bleach episodes (season 4)|List of Bleach episodes (season 4)]]
+* [[Wikipedia:Featured list candidates/List of Brazilian states by Human Development Index|List of Brazilian states by Human Development Index]]
-:INSTANCE: A graph <math>G=(V,E)</math> and a positive integer <math>k</math>.
+{{multicol-break}}
-:QUESTION: Does G admit a biclique edge cover containing at most <math>k</math> bicliques?
+* [[Wikipedia:Featured list candidates/Alabama Crimson Tide football seasons|Alabama Crimson Tide football seasons]]
+* [[Wikipedia:Featured list candidates/Arizona Diamondbacks seasons|Arizona Diamondbacks seasons]]
-This problem is [[NP-complete]], even for [[bipartite graph]]s, as proved by Orlin. It appears as problem '''GT18''' in
+* [[Wikipedia:Featured list candidates/List of D.Gray-man chapters|List of D.Gray-man chapters]]
-Garey and Johnson's classical book on NP-completeness. This decision problem is a rather straightforward reformulation of
+* [[Wikipedia:Featured list candidates/Mark of the Year|Mark of the Year]]
-another decision problem on families of finite sets, the ''set basis problem'', proved
+* [[Wikipedia:Featured list candidates/List of D.Gray-man episodes|List of D.Gray-man episodes]]
-to be NP-complete earlier by Stockmeyer, and appearing as problem '''SP7''' in Garey and Johnson's book.
+* [[Wikipedia:Featured list candidates/List of universities in Quebec|List of universities in Quebec]]
+* [[Wikipedia:Featured list candidates/List of universities in British Columbia|List of universities in British Columbia]]
-:INSTANCE: A collection of finite sets <math>S_1,\ldots,S_n</math> and a positive integer <math>k</math>.
+* [[Wikipedia:Featured list candidates/List of awards and nominations received by Justice|List of awards and nominations received by Justice]]
-:QUESTION: Can we choose at most <math>k</math> subsets such that their union equals <math>\bigcup_{i=1}^n S_i</math>, the union of all <math>S_i</math>?
+* [[Wikipedia:Featured list candidates/List of awards and nominations received by Blink-182|List of awards and nominations received by Blink-182]]
-<!-- too technical?
+* [[Wikipedia:Featured list candidates/List of S.H.E awards|List of S.H.E awards]]
-To transform a bipartite graph <math>G=(U,V,E)</math> into an instance of the latter problem, simply take
+{{multicol-end}}
-<math>U = \bigcup_{i=1}^n S_i</math>, <math>V=\{S_1,\ldots, S_n\}</math>,
-and <math> \{\{u,S_i\} \mid u \in S_i\}</math> as edge set. The converse direction is similar.
--->
-==References==
-* P. C. Fishburn and P. L. Hammer. Bipartite dimensions and bipartite degrees of graphs. ''Discrete Mathematics'', 160:127-148, 1996
-* M. R. Garey and D. S. Johnson. ''[[Computers and Intractability: A Guide to the Theory of NP-Completeness]]''. Freeman, 1979.
-* S. Monson, N. Pullman, and R. Rees: A survey of clique and biclique coverings and factorizations of (0,1)-matrices. ''Bulletin of the ICA'', vol 14, pp. 17--86, 1995.
-* J. Orlin. Contentment in Graph Theory: Covering Graphs with Cliques. ''Indagationes Mathematicae'', 80:406–424, 1977.
-* Larry J. Stockmeyer. The set basis problem is NP-complete. Technical Report RC-5431, IBM, 1975.
-==See also==
-[[List of NP-complete problems]]
-==External Links==
-[http://11011110.livejournal.com/134829.html blog entry about bipartite dimension by David Eppstein]