Abstract | ||
---|---|---|
For a graph G of order n and an integer ℓ≥1, the ℓ-chord interval of a set of vertices S of G is the set formed by S and the vertices of any path between two vertices of S having chords of length at most ℓ. The ℓ-chord interval number of G is the cardinality of a minimum set whose ℓ-chord interval is equal to V(G). If S is equal to its ℓ-chord interval, then S is ℓ-chord convex. The ℓ-chord convex hull of S is the minimum ℓ-chord convex set containing S. Our main contributions are polynomial-time algorithms for computing the (n−ℓ)-chord interval of S and the (n−ℓ)-chord interval number of G when ℓ is upper bounded by a constant, and computing the ℓ-chord convex hull of S when ℓ is part of the input. |
Year | DOI | Venue |
---|---|---|
2020 | 10.1016/j.dam.2020.04.022 | Discrete Applied Mathematics |
Keywords | DocType | Volume |
Convex hull,Interval number,Monophonic convexity,Triangle path convexity | Journal | 284 |
ISSN | Citations | PageRank |
0166-218X | 0 | 0.34 |
References | Authors | |
0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Mitre Dourado | 1 | 90 | 18.43 |
Rodolfo Alves de Oliveira | 2 | 4 | 1.45 |