74:"A much easier problem to solve is that of finding a maximal independent set, which is an independent set not contained in any other independent set. We begin with a single vertex. We find a vertex not adjacent to it and add it, then find a vertex adjacent to neither of these and add it, and so on until we can find no more vertices to add. At this time the set is maximal independent."
111:
into this article. There seems to be no discussion about this proposal. I for one am opposed to such a merge. Independent sets are very important in graph theory and have many applications; the independent set problem is simply one computational problem about independent sets. I think that keeping
77:
This seems to be incorrect. Consider the set a--b--c, which has three nodes (a, b, c) and two edges (a-b, b-c). According to this description, we first pick an arbitrary single vertex. For this example, we pick b. There are no non-adjacent nodes left in the set, and so we conclude that the set
49:
exists, then we know the set contains exactly one literal from each clause (because it cannot contain two literals from the same clause), so we can make those literals true (and the other literals either true or false, it doesn't matter) to get a satisfying assignment for all the literals. The
210:)? It's definitely not complete since all pages of these problems should be augmented with the corresponding linear program formulation. And more importantly, there should be an explanation for the covering-packing duality. Still I think it helps a lot to see these problems side by side.
82:{b} is a maximal independent set, since it is not contained in any other independent set. It is not a maximum independent set (which is probably what you mean by "maximally independent"), but that wasn't claimed. --
21:
It seems that the NP-hardness proof is incorrect. There seems to be an assumption that at most one literal can be true in a clause. I think whoever wrote the proof got the literals and their complements mixed up.
139:- these two articles, while related, are clearly different and address different fields, and should not be merged (especially not the suggested direction!). There is a link from
45:
The proof is correct; no such assumption is being made. Edges are drawn between literals in the same clause so that, if an independent set of size
37:
159:
says, the study of independent sets is far vaster than just this one problem, and as such I feel the current mention suffices.
206:
What do you think of my idea to have a box of the most prominent covering problems and their corresponding dual problems (see
33:
189:
207:
144:
113:
29:
164:
160:
25:
185:
54:
of the true literals in a satisfying assignment, not necessarily the entire set of true literals. —
148:
97:
215:
177:
152:
140:
125:
117:
108:
59:
78:(b) is maximally independent. However, the set (a, c) is really maximally independent.
181:
112:
two separate articles is best. If a merge is strongly desired, I would suggest merging
151:
feels this should be more prominently featured, ze can of course change the layout of
219:
193:
168:
129:
86:
63:
83:
176:, but with Bkell’s suggestion of having the algorithmic aspect as a section of
211:
156:
136:
121:
55:
101:
104:
93:
Proposal to merge "Independent set" into this article
180:, rather than the other way around. Check out
8:
7:
155:to reflect this importance, but as
14:
50:independent set corresponds to a
17:NP-hardness proof is incorrect?
1:
194:20:16, 12 December 2008 (UTC)
120:, not the other way around. —
87:22:32, 27 October 2006 (UTC)
64:02:37, 14 August 2008 (UTC)
235:
220:18:18, 11 March 2009 (UTC)
202:Covering-Packing Dualities
169:15:58, 22 July 2008 (UTC)
130:05:01, 22 July 2008 (UTC)
208:independent set problem
145:Independent set problem
114:Independent set problem
40:) 01:24, 14 August 2008
100:has proposed (on
41:
28:comment added by
226:
184:for an example.
23:
234:
233:
229:
228:
227:
225:
224:
223:
204:
178:Independent set
153:Independent set
141:Independent set
118:Independent set
109:Independent set
95:
72:
30:203.143.165.107
19:
12:
11:
5:
232:
230:
203:
200:
199:
198:
197:
196:
186:Thore Husfeldt
182:Graph coloring
94:
91:
90:
89:
71:
68:
67:
66:
18:
15:
13:
10:
9:
6:
4:
3:
2:
231:
222:
221:
217:
213:
209:
201:
195:
191:
187:
183:
179:
175:
172:
171:
170:
166:
162:
158:
154:
150:
146:
142:
138:
135:I agree with
134:
133:
132:
131:
127:
123:
119:
115:
110:
106:
103:
99:
92:
88:
85:
81:
80:
79:
75:
69:
65:
61:
57:
53:
48:
44:
43:
42:
39:
35:
31:
27:
16:
205:
173:
96:
76:
73:
70:Other issues
51:
46:
20:
107:) to merge
24:—Preceding
102:16 April
38:contribs
26:unsigned
174:Support
147:... if
143:to the
149:Twanvl
98:Twanvl
84:Mellum
52:subset
212:ylloh
157:Bkell
137:Bkell
122:Bkell
116:into
56:Bkell
216:talk
190:talk
165:talk
161:Mica
126:talk
105:2008
60:talk
34:talk
218:)
192:)
167:)
128:)
62:)
36:•
214:(
188:(
163:(
124:(
58:(
47:k
32:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.