𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A polynomial algorithm for the extendability problem in bipartite graphs

✍ Scribed by J. Lakhal; L. Litzler

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
587 KB
Volume
65
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

Let G = [ y E] be a simple connected graph and let k be an integer such that 0 < k < 1 VI /2. G is said to be k-extendable if it contains a perfect matching and every matching of k edges extends to, i.e. is a subset of, a perfect matching. The extendability problem consists in finding the maximum value of k, denoted ~JJ, such that G is k-extendable. We give in this paper the first polynomial algorithm for the extendability problem when the graph is bipartite. Its complexity is 0( rn. min( G + n, hi. n) ) where n and m designate the number of vertices and edges of the graph respectively. Furthermore, if a perfect matching or a special orientation of the edges are known then this algorithm can be run in parallel in 0( k~. log n) time using a polynomial number of processors on a concurrent-read concurrent-write PRAM machine. @

πŸ“œ SIMILAR VOLUMES

A solution to Gutman's problem on the ch
A solution to Gutman's problem on the characteristic polynomial of a bipartite graph
✍ Xueliang Li; Heping Zhang πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 209 KB

In this short paper, we present a solution to Gutman's problem on the characteristic polynomial of a bipartite graph (Research Problem 134, Discrete Math. 88 (1991)). In [2] I. Gutman proposed a research problem which is stated as follows. The matchings polynomial of a graph G is defined by cl(G,x)

A polynomial algorithm for the minimum w
A polynomial algorithm for the minimum weighted clique cover problem on claw-free perfect graphs
✍ Wen-Lian HSU; George L. Nemhauser πŸ“‚ Article πŸ“… 1982 πŸ› Elsevier Science 🌐 English βš– 688 KB

Discrete Mathematics 3X ( 19X2) 6S-71 North-Holland Publishing Company 65 Let G = (V, E) be a graph with a positive number wt(v) assigned to each L' E V. A weighted clique saver of the vertices of G is a collection of cliques with a non-negative weight yC. assigned to each clique C in the collection