Name
Abstract | ||
|---|---|---|
A bipartite graph G=(U,V,E) is a chain graph [M. Yannakakis, Computing the minimum fill-in is NP-complete, SIAM J. Algebraic Discrete Methods 2 (1) (1981) 77-79] if there is a bijection @p:{1,...,|U|}-U such that @C(@p(1))@?@C(@p(2))@?...@?@C(@p(|U|)), where @C is a function that maps a node to its neighbors. We give approximation algorithms for two variants of the Minimum Chain Completion problem, where we are given a bipartite graph G(U,V,E), and the goal is find the minimum set of edges F that need to be added to G such that the bipartite graph G^'=(U,V,E^') (E^'=E@?F) is a chain graph. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.ipl.2009.05.006 | Inf. Process. Lett. |
Keywords | Field | DocType |
chain graphs,minimum fill-in,min cut,chain graph,approximation algorithm,minimum set,vertex cover,bipartite graph,m. yannakakis,siam j. algebraic discrete,edges f,minimum chain completion problem,max ∞ow,approximation algorithms,max flow | Approximation algorithm,Discrete mathematics,Combinatorics,Algebraic number,Bijection,Vertex (geometry),Bound graph,Bipartite graph,Vertex cover,Maximum flow problem,Mathematics | Journal |
Volume | Issue | ISSN |
109 | 17 | 0020-0190 |
Citations | PageRank | References |
4 | 0.51 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tomás Feder | 1 | 1959 | 184.99 |
| Heikki Mannila | 2 | 6595 | 1495.69 |
| Evimaria Terzi | 3 | 1580 | 83.54 |