Name
Abstract | ||
|---|---|---|
The authors give a Gallai-Edmonds type structure theorem on (1,f)-odd subgraphs and a polynomial algorithm for finding an optimal (1,f)-odd subgraph. Lovasz [The factorization of graphs. II. Acta Math. Acad. Sci. Hungar. 23 (1972) 223-246] and Cornuejols [General factors of graphs, J. Combin. Theory Ser. B 45(2) (1988) 185-198] solved these problems for a more general problem, the general factor problem with gaps at most 1. However, the statements of the theorems and the algorithm are much more simple in this special case, so it is worth of interest on its own. Also, the algorithm given for this case is faster than the general algorithm. The proofs follow a direct approach instead of deducing from the general case. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.disc.2005.11.078 | Discrete Mathematics |
Keywords | Field | DocType |
generalized matching algorithm,( 1,gallai-edmonds type structure theorem,gallai–edmonds type structure theorem,f )-odd subgraphs,(1,f ) -odd subgraphs,generic algorithm | Structured program theorem,Direct method,Discrete mathematics,Graph,Combinatorics,General algorithm,Algorithm,Mathematical proof,Factorization,Polynomial algorithm,Mathematics,Special case | Journal |
Volume | Issue | ISSN |
307 | 11-12 | Discrete Mathematics |
Citations | PageRank | References |
3 | 0.59 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mikio Kano | 1 | 548 | 99.79 |
| G.Y. Katona | 2 | 24 | 4.77 |