Vertex-Weighted Graphs: Realizable and Unrealizable Domains: Realizable and Unrealizable Domains

Amotz Bar-Noy, David Peleg, Dror Rawitz

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمر


Consider the following natural variation of the degree realization problem. Let G=(V,E)G=(V,E) be a simple undirected graph of order n. Let f∈Rn≥0f∈R≥0n be a vector of vertex requirements, and let w∈Rn≥0w∈R≥0n be a vector of provided services at the vertices. Then w satisfies f on G if the constraints ∑j∈N(i)wj=fi∑j∈N(i)wj=fi are satisfied for all i∈Vi∈V, where N(i) denotes the neighborhood of i. Given a requirements vector f, the WEIGHTED GRAPH REALIZATION problem asks for a suitable graph G and a vector w of provided services that satisfy f on G. In [7] it is observed that any requirement vector where n is even can be realized. If n is odd, the problem becomes much harder. For the unsolved cases, the decision of whether f is realizable or not can be formulated as whether fnfn (the largest requirement) lies within certain intervals. In [5] some intervals are identified where f can be realized, and their complements form n−32n−32 connected intervals (“unknown domains”) which we give odd indices k=1,3,…,n−4k=1,3,…,n−4. The unknown domain for k=1k=1 is shown to be unrealizable. Our main result presents structural properties that a graph must have if it realizes a vector in one of these unknown domains for k≥3k≥3. The unknown domains are characterized by inequalities which we translate to graph properties. Our analysis identifies several realizable sub-intervals, and shows that each of the unknown domains has at least one sub-interval that cannot be realized.
اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفWALCOM: Algorithms and Computation
العنوان الفرعي لمنشور المضيفAlgorithms and Computation - 16th International Conference and Workshops, WALCOM 2022, Proceedings
المحررونPetra Mutzel, Md. Saidur Rahman, Slamin
ناشرSpringer Science and Business Media Deutschland GmbH
عدد الصفحات13
رقم المعيار الدولي للكتب (الإلكتروني)9783030967314
رقم المعيار الدولي للكتب (المطبوع)3030967301, 9783030967307
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2022
الحدث16th International Conference and Workshops, WALCOM 2022 - Jember, Indonesia
المدة: ٢٤ مارس ٢٠٢٢٢٦ مارس ٢٠٢٢

سلسلة المنشورات

الاسمLecture Notes in Computer Science
مستوى الصوت13174
رقم المعيار الدولي للدوريات (المطبوع)0302-9743


!!Conference16th International Conference and Workshops, WALCOM 2022

All Science Journal Classification (ASJC) codes

  • !!Theoretical Computer Science
  • !!General Computer Science


أدرس بدقة موضوعات البحث “Vertex-Weighted Graphs: Realizable and Unrealizable Domains: Realizable and Unrealizable Domains'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا