Convex bipartite graph
Source 📝
447:
407:
365:
419:
379:
488:
371:
517:
292:(August 1981). "Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems".
512:
481:
507:
395:
474:
289:
319:
275:
411:
415:
375:
344:
309:
301:
29:
458:
400:
349:
332:
501:
323:
454:
21:
17:
333:"Bipartite permutation graphs with application to the minimum buffer size problem"
53:
177:
305:
314:
446:
462:
399:
127:) be a bipartite graph, i.e., the vertex set is
32:with specific properties. A bipartite graph, (
482:
8:
44:), is said to be convex over the vertex set
331:Ten-hwang Lai; Shu-shang Wei (April 1997).
75:is defined analogously. A bipartite graph (
489:
475:
398:; Van Bang Le; Jeremy P. Spinrad (1999).
348:
313:
156:) denote the neighborhood of a vertex
7:
443:
441:
14:
445:
432:convex if there is an ordering.
367:Efficient graph representations
176:if and only if there exists a
1:
350:10.1016/S0166-218X(96)00014-5
461:. You can help Knowledge by
337:Discrete Applied Mathematics
87:) that is convex over both
534:
440:
364:Jeremy P. Spinrad (2003).
64:the vertices adjacent to
374:Bookstore. p. 128.
402:Graph classes: a survey
225:there does not exist a
200:, for any two vertices
457:-related article is a
192:|}, such that for all
26:convex bipartite graph
188: → {1, …, |
143: = ∅. Let
290:Franco P. Preparata
518:Graph theory stubs
396:Andreas Brandstädt
306:10.1007/BF00264533
276:Convex plane graph
56:such that for all
470:
469:
421:978-0-89871-432-6
381:978-0-8218-2815-1
258:) <
250:) <
107:Formal definition
68:are consecutive.
525:
513:Bipartite graphs
491:
484:
477:
449:
442:
434:
429:
428:
405:
391:
389:
388:
360:
358:
357:
352:
327:
317:
294:Acta Informatica
533:
532:
528:
527:
526:
524:
523:
522:
498:
497:
496:
495:
438:
426:
424:
422:
394:
386:
384:
382:
363:
355:
353:
330:
288:W. Lipski Jr.;
287:
284:
272:
237:
216:
151:
109:
71:Convexity over
30:bipartite graph
12:
11:
5:
531:
529:
521:
520:
515:
510:
508:Graph families
500:
499:
494:
493:
486:
479:
471:
468:
467:
450:
436:
435:
420:
392:
380:
361:
328:
300:(4): 329–346.
283:
280:
279:
278:
271:
268:
233:
221:) ⊆
212:
147:
115: = (
108:
105:
95:is said to be
13:
10:
9:
6:
4:
3:
2:
530:
519:
516:
514:
511:
509:
506:
505:
503:
492:
487:
485:
480:
478:
473:
472:
466:
464:
460:
456:
451:
448:
444:
439:
433:
423:
417:
413:
409:
404:
403:
397:
393:
383:
377:
373:
369:
368:
362:
351:
346:
342:
338:
334:
329:
325:
321:
316:
311:
307:
303:
299:
295:
291:
286:
285:
281:
277:
274:
273:
269:
267:
265:
261:
257:
253:
249:
245:
241:
236:
232:
229: ∉
228:
224:
220:
215:
211:
208: ∈
207:
203:
199:
196: ∈
195:
191:
187:
183:
179:
175:
171:
167:
164:. The graph
163:
160: ∈
159:
155:
150:
146:
142:
139: ∩
138:
134:
131: ∪
130:
126:
122:
119: ∪
118:
114:
106:
104:
102:
101:doubly convex
98:
94:
90:
86:
82:
79: ∪
78:
74:
69:
67:
63:
60: ∈
59:
55:
51:
47:
43:
39:
36: ∪
35:
31:
27:
23:
19:
463:expanding it
455:graph theory
452:
437:
431:
425:. Retrieved
401:
385:. Retrieved
366:
354:. Retrieved
343:(1): 33–55.
340:
336:
297:
293:
263:
259:
255:
251:
247:
243:
242:) such that
239:
234:
230:
226:
222:
218:
213:
209:
205:
201:
197:
193:
189:
185:
181:
173:
169:
165:
161:
157:
153:
148:
144:
140:
136:
132:
128:
124:
120:
116:
112:
110:
100:
96:
92:
88:
84:
80:
76:
72:
70:
65:
61:
57:
49:
45:
41:
37:
33:
25:
22:graph theory
18:mathematical
15:
502:Categories
427:2009-07-20
410:. p.
387:2009-07-20
356:2009-07-20
315:2142/74215
282:References
54:enumerated
180:mapping,
178:bijective
20:field of
324:39361123
270:See also
97:biconvex
184::
123:,
83:,
52:can be
40:,
16:In the
418:
378:
322:
170:convex
135:where
453:This
320:S2CID
172:over
28:is a
459:stub
416:ISBN
408:SIAM
376:ISBN
111:Let
91:and
24:, a
372:AMS
345:doi
310:hdl
302:doi
266:).
168:is
99:or
48:if
504::
430:.
414:.
412:94
406:.
370:.
341:74
339:.
335:.
318:.
308:.
298:15
296:.
103:.
490:e
483:t
476:v
465:.
390:.
359:.
347::
326:.
312::
304::
264:y
262:(
260:f
256:z
254:(
252:f
248:x
246:(
244:f
240:v
238:(
235:G
231:N
227:z
223:U
219:v
217:(
214:G
210:N
206:y
204:,
202:x
198:V
194:v
190:U
186:U
182:f
174:U
166:G
162:V
158:v
154:v
152:(
149:G
145:N
141:V
137:U
133:V
129:U
125:E
121:V
117:U
113:G
93:V
89:U
85:E
81:V
77:U
73:V
66:v
62:V
58:v
50:U
46:U
42:E
38:V
34:U
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
↑
