the forwarding indices of graphs - a survey

مؤشرات إعادة التوجيه في المخططات - دراسة مسحية

Clicks: 312
ID: 194032
2013
Article Quality & Performance Metrics
Overall Quality
Not rated
Combines reader engagement with the AI quality analysis. This article has not been analysed, so there is no overall score — reader engagement is measured and shown alongside.
AI Quality Assessment
Not analyzed
Readership in this journal
Steady

Ranked #18 of 95 articles by views in zhonghua yi xue za zhi

Most read Least read

Bar heights use a square-root scale.

Mint this article as an NFT
Not yet minted

Create a permanent, verifiable on-chain record of this article on the Scimatic Network. The NFT is held in your Journament account, and you can withdraw it to your own wallet at any time.

5 SUSD one-off · no wallet required
Abstract
A routing \(R\) of a connected graph \(G\) of order \(n\) is a collection of \(n(n-1)\) simple paths connecting every ordered pair of vertices of \(G\). The vertex-forwarding index \(\xi(G,R)\) of \(G\) with respect to a routing \(R\) is defined as the maximum number of paths in \(R\) passing through any vertex of \(G\). The vertex-forwarding index \(\xi(G)\) of \(G\) is defined as the minimum \(\xi(G,R)\) over all routings \(R\) of \(G\). Similarly, the edge-forwarding index \(\pi(G,R)\) of \(G\) with respect to a routing \(R\) is the maximum number of paths in \(R\) passing through any edge of \(G\). The edge-forwarding index \(\pi(G)\) of \(G\) is the minimum \(\pi(G,R)\) over all routings \(R\) of \(G\). The vertex-forwarding index or the edge-forwarding index corresponds to the maximum load of the graph. Therefore, it is important to find routings minimizing these indices and thus has received much research attention for over twenty years. This paper surveys some known results on these forwarding indices, further research problems and several conjectures, also states some difficulty and relations to other topics in graph theory.
يُعرَّف التوجيه \(R\) لمخطط متصل \(G\) من الرتبة \(n\) بأنه مجموعة مكونة من \(n(n-1)\) من المسارات البسيطة التي تربط بين كل زوج مرتب من رؤوس \(G\). ويُعرَّف مؤشر تمرير الرؤوس \(\xi(G,R)\) للمخطط \(G\) بالنسبة إلى التوجيه \(R\) بأنه أقصى عدد من المسارات في \(R\) المارة بأي رأس من رؤوس \(G\). كما يُعرَّف مؤشر تمرير الرؤوس \(\xi(G)\) للمخطط \(G\) بأنه القيمة الصغرى لـ \(\xi(G,R)\) على جميع التوجيهات \(R\) الممكنة للمخطط \(G\). وبالمثل، فإن مؤشر تمرير الحواف \(\pi(G,R)\) للمخطط \(G\) بالنسبة إلى التوجيه \(R\) هو أقصى عدد من المسارات في \(R\) المارة بأي حافة من حواف \(G\). ومؤشر تمرير الحواف \(\pi(G)\) للمخطط \(G\) هو القيمة الصغرى لـ \(\pi(G,R)\) على جميع التوجيهات \(R\) للمخطط \(G\). يقابل مؤشر تمرير الرؤوس أو مؤشر تمرير الحواف الحِمل الأقصى للمخطط؛ ولذلك، تكمن الأهمية في إيجاد توجيهات تُقلِّل هذه المؤشرات إلى الحد الأدنى، وهو ما حظي باهتمام بحثي كبير لأكثر من عشرين عاماً. تستعرض هذه الورقة بعض النتائج المعروفة حول مؤشرات التمرير هذه، ومشكلات بحثية إضافية، وعدة حدسيات، كما توضح بعض الصعوبات والصلات بموضوعات أخرى في نظرية المخططات.
Reference Key
xu2013opusculathe Use this key to autocite in the manuscript while using SciMatic Manuscript Manager or Thesis Manager
Authors
Journal zhonghua yi xue za zhi
Year 2013
DOI
http://dx.doi.org/10.7494/OpMath.2013.33.2.345
URL
Keywords

Citations

No citations found. To add a citation, contact the admin at info@scimatic.org

No comments yet. Be the first to comment on this article.