Discrete Integral and Discrete Derivative on Graphs and Switch Problem of Trees

M. H. Khalifeh () and Abdol-Hossein Esfahanian
Additional contact information
M. H. Khalifeh: Department of Computer Science and Engineering, Michigan State University, East Lansing, MI 48824, USA
Abdol-Hossein Esfahanian: Department of Computer Science and Engineering, Michigan State University, East Lansing, MI 48824, USA

Mathematics, 2023, vol. 11, issue 7, 1-19

Abstract: For a vertex and edge weighted (VEW) graph G with a vertex weight function f G let W α , β ( G ) = ∑ { u , v } ⊆ V ( G ) [ α f G ( u ) × f G ( v ) + β ( f G ( u ) + f G ( v ) ) ] d G ( u , v ) where, α , β ∈ ℝ and d G ( u , v ) denotes the distance, the minimum sum of edge weights across all the paths connecting u , v ∈ V ( G ) . Assume T is a VEW tree, and e ∈ E ( T ) fails. If we reconnect the two components of T − e with new edge ϵ ≠ e such that, W α , β ( T ϵ \ e = T − e + ϵ ) is minimum, then ϵ is called a best switch (BS) of e w.r.t. W α , β . We define three notions: convexity, discrete derivative, and discrete integral for the VEW graphs. As an application of the notions, we solve some BS problems for positively VEW trees. For example, assume T is an n -vertex VEW tree. Then, for the inputs e ∈ E ( T ) and w , α , β ∈ ℝ + , we return ϵ , T ϵ \ e , and W α , β ( T ϵ \ e ) with the worst average time of O ( log n ) and the best time of O ( 1 ) where ϵ is a BS of e w.r.t. W α , β and the weight of ϵ is w .

Keywords: discrete derivative; discrete integral; best switch; convex graph; weighted total distance; weighted tree (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/7/1678/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/7/1678/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:7:p:1678-:d:1112892

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().