Name
Abstract | ||
|---|---|---|
We prove terminal Δ-Y reducibility of planar graphs with at most three terminals. The most important consequence of our proof is that this implicitly gives an efficient algorithm with time complexity O(|E(G)|4) for reducibility of planar graphs G with at most three terminals. It also can be used for restricted reducibility problems with more terminals. Our proof uses a very well-known translation from these operations to transformations on the medial graph. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 57(2), 174–186 2011 © 2011 Wiley Periodicals, Inc. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1002/net.20399 | Networks |
Keywords | Field | DocType |
medial graph,time complexity o,y reducibility,wiley periodicals,inc. networks,restricted reducibility problem,planar graph,terminal delta-wye reducibility,well-known translation,efficient algorithm,important consequence,network reliability,planar graphs,topological graph theory,graph theory,series parallel | Discrete mathematics,Outerplanar graph,Combinatorics,Forbidden graph characterization,Planar straight-line graph,Book embedding,Pathwidth,1-planar graph,Universal graph,Mathematics,Planar graph | Journal |
Volume | Issue | ISSN |
57 | 2 | 0028-3045 |
Citations | PageRank | References |
3 | 0.42 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Isidoro Gitler | 1 | 29 | 7.03 |
| Feliu Sagols | 2 | 4 | 1.58 |