Name
Abstract | ||
|---|---|---|
Let G be a connected graph and S subset of or equal to V(G). Then the Steiner distance of S in G, denoted by d(G)(S), is the smallest number of edges in a connected subgraph of G that contains S. A connected graph is k-Steiner distance hereditary, k greater than or equal to 2, if for every S subset of or equal to V(G) such that \S\ = k and every connected induced subgraph H of G containing S, d(H)(S) = d(G)(S). A polynomial algorithm for testing whether a graph is 3-Steiner distance hereditary is developed. In addition, a polynomial algorithm for testing whether an arbitrary graph has a cycle of length exceeding t, for any fixed t, without crossing chords is provided. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1016/0020-0190(95)00071-J | Inf. Process. Lett. |
Keywords | Field | DocType |
polynomial algorithm,3-steiner distance,algorithms,connected graph | Discrete mathematics,Combinatorics,k-vertex-connected graph,Graph power,Graph factorization,k-edge-connected graph,Distance-hereditary graph,Distance-regular graph,Factor-critical graph,Butterfly graph,Mathematics | Journal |
Volume | Issue | ISSN |
55 | 3 | 0020-0190 |
Citations | PageRank | References |
2 | 0.66 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ortrud Oellermann | 1 | 12 | 2.51 |
| Jeremy P. Spinrad | 2 | 1342 | 115.52 |