84:
74:
53:
22:
171:-- This definition may give the impression that every bipartite graph has a perfect matching, which is not true. Does this mean that the Dulmage–Mendelsohn decomposition is defined only on such graphs that have a perfect matching? If so, then this should be stated clearly in order to prevent confusion. --
209:
I realized, to my horror, that Bunus and
Fritzson (see additional link 1 in the article) were terribly wrong in their 2002 paper, as they were in the one before that ("A Debugging Scheme for Declarative Equation-Based Modeling Languages"). In both of these articles, they use the algorithm with sets
186:
The DM decomposition indeed applies to any bipartite graph; even better, in practice, the coarse decomposition is only useful when no perfect matching exists (including, but not limited to, non-square cases). It is stated that one input of the algorithm is D, 'the set of vertices in G that are not
210:
E, U and O that has been, since, published by Irving et al. ("Rank-Maximal
Matchings", 2006), and talk about this algorithm as "the Dulmage-Mendelsohn decomposition algorithm". It is not. Not only the article by Irving does not mention Dulmage nor Mendelsohn at any point, but
187:
matched in at least one maximum matching of G'. If perfect matchings exist, then D is an empty set and the coarse DM decomposition is trivial; then any finer decomposition roughly consists in finding
Strongly Connected Components, i.e., calling Tarjan to the rescue.
217:(For those who would like to check: the DM decomposition of this example is {e4,eq5,eq6,eq7} as the underdetermined part, {eq1,eq2,eq3} as the overdetermined part, no square/enabled part in between. I also checked these results with Matlab 2018a.)
163:"the Dulmage–Mendelsohn decomposition is a partition of the vertices of a bipartite graph into subsets, with the property that two adjacent vertices belong to the same subset if and only if they are paired with each other
140:
220:
To my knowledge, the works by Bunus and
Fritzson are the only reason why this 'alternative DM decomposition' is mentioned in the Knowledge article, and it is actually wrong. As such,
206:
I am currently working, as a post-doctoral student, on the modeling and simulation of physical systems, and as such, I had to come back to the gool old DM decomposition.
227:
Of course, I highly encourage you to check the veracity of what I just wrote before taking any decision, and as a non-registered user, I will not edit the page myself.
212:
the results yielded by this algorithm differ from the canonical DM decomposition, even on the very exemple provided by Bunus and
Fritzson in their 2002 paper
258:
130:
253:
106:
231:
188:
97:
58:
33:
235:
192:
21:
239:
196:
180:
39:
83:
176:
105:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
89:
73:
52:
172:
247:
102:
79:
15:
222:
this whole section should be removed from the article
101:, a collaborative effort to improve the coverage of
8:
19:
47:
49:
7:
95:This article is within the scope of
202:Factual error: alternate definition
38:It is of interest to the following
165:in a perfect matching of the graph
14:
259:Low-priority mathematics articles
115:Knowledge:WikiProject Mathematics
254:Start-Class mathematics articles
118:Template:WikiProject Mathematics
82:
72:
51:
20:
135:This article has been rated as
1:
181:16:42, 28 December 2013 (UTC)
109:and see a list of open tasks.
275:
240:08:31, 19 March 2020 (UTC)
197:08:36, 19 March 2020 (UTC)
134:
67:
46:
158:Applicable to any graph?
141:project's priority scale
98:WikiProject Mathematics
28:This article is rated
230:Thanks for reading.
121:mathematics articles
90:Mathematics portal
34:content assessment
155:
154:
151:
150:
147:
146:
266:
123:
122:
119:
116:
113:
92:
87:
86:
76:
69:
68:
63:
55:
48:
31:
25:
24:
16:
274:
273:
269:
268:
267:
265:
264:
263:
244:
243:
204:
160:
120:
117:
114:
111:
110:
88:
81:
61:
32:on Knowledge's
29:
12:
11:
5:
272:
270:
262:
261:
256:
246:
245:
232:92.167.218.166
203:
200:
189:92.167.218.166
185:
169:
168:
159:
156:
153:
152:
149:
148:
145:
144:
133:
127:
126:
124:
107:the discussion
94:
93:
77:
65:
64:
56:
44:
43:
37:
26:
13:
10:
9:
6:
4:
3:
2:
271:
260:
257:
255:
252:
251:
249:
242:
241:
237:
233:
228:
225:
223:
218:
215:
213:
207:
201:
199:
198:
194:
190:
183:
182:
178:
174:
166:
162:
161:
157:
142:
138:
132:
129:
128:
125:
108:
104:
100:
99:
91:
85:
80:
78:
75:
71:
70:
66:
60:
57:
54:
50:
45:
41:
35:
27:
23:
18:
17:
229:
226:
221:
219:
216:
211:
208:
205:
184:
170:
164:
137:Low-priority
136:
96:
62:Low‑priority
40:WikiProjects
112:Mathematics
103:mathematics
59:Mathematics
30:Start-class
248:Categories
173:Erel Segal
139:on the
36:scale.
236:talk
193:talk
177:talk
131:Low
250::
238:)
224:.
214:.
195:)
179:)
234:(
191:(
175:(
167:"
143:.
42::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
