Feedback arc set

In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks all of the cycles, producing an acyclic subgraph of the given graph, often called a directed acyclic graph. A feedback arc set with the fewest possible edges is a minimum feedback arc set and its removal leaves a maximum acyclic subgraph; weighted versions of these optimization problems are also used. If a feedback arc set is minimal, meaning that removing any edge from it produces a subset that is not a feedback arc set, then it has an additional property: reversing all of its edges, rather than removing them, produces a directed acyclic graph.

Feedback arc sets have applications in circuit analysis, chemical engineering, deadlock resolution, ranked voting, ranking competitors in sporting events, mathematical psychology, ethology, and graph drawing. Finding minimum feedback arc sets and maximum acyclic subgraphs is NP-hard; it can be solved exactly in exponential time, or in fixed-parameter tractable time. In polynomial time, the minimum feedback arc set can be approximated to within a polylogarithmic approximation ratio, and maximum acyclic subgraphs can be approximated to within a constant factor. Both are hard to approximate closer than some constant factor, an inapproximability result that can be strengthened under the unique games conjecture. For tournament graphs, the minimum feedback arc set can be approximated more accurately, and for planar graphs both problems can be solved exactly in polynomial time.

A closely related problem, the feedback vertex set, is a set of vertices containing at least one vertex from every cycle in a directed or undirected graph. In undirected graphs, the spanning trees are the largest acyclic subgraphs, and the number of edges removed in forming a spanning tree is the circuit rank.

Applications

يمكن حلّ العديد من المشكلات المتعلقة بالتصنيفات أو الترتيبات من خلال إيجاد مجموعة أقواس التغذية الراجعة على رسم بياني للمنافسة ، وهو رسم بياني موجه ذو حافة واحدة بين كل زوج من الرؤوس. يؤدي عكس حواف مجموعة أقواس التغذية الراجعة إلى إنتاج رسم بياني موجه غير دوري، ويمكن استخدام ترتيبه الطوبولوجي الفريد كترتيب مطلوب. تشمل تطبيقات هذه الطريقة ما يلي:

في المنافسات الرياضية التي تُقام بنظام الدوري ، تُسجَّل نتائج كل مباراة بتوجيه حافة من الخاسر إلى الفائز. يُنتج عن إيجاد مجموعة أقواس التغذية الراجعة الدنيا في الرسم البياني الناتج، وعكس حوافها، والترتيب الطوبولوجي، تصنيفًا لجميع المتنافسين. من بين جميع طرق اختيار التصنيف، تُقلِّل هذه الطريقة من إجمالي عدد المفاجآت، أي المباريات التي يفوز فيها متنافس ذو تصنيف أدنى على متنافس ذي تصنيف أعلى. ^{[ 2 ]}^{[ 3 ]}^{[ 4 ]} تستخدم العديد من الرياضات طرقًا أبسط لأنظمة تصنيف البطولات الجماعية بناءً على النقاط الممنوحة لكل مباراة؛ ^{[ 5 ]} ويمكن لهذه الطرق أن تُقدِّم تقريبًا ثابتًا لتصنيف الحد الأدنى من المفاجآت. ^{[ 6 ]}
في علم الرئيسيات، وبشكل أعم في علم السلوك الحيواني ، غالباً ما تُحدد التسلسلات الهرمية للهيمنة من خلال البحث عن ترتيب بأقل عدد من الانعكاسات في سلوك الهيمنة الملاحظ، وهو شكل آخر من أشكال مشكلة مجموعة أقواس التغذية الراجعة الدنيا. ^{[ 7 ]}^{[ 8 ]}^{[ 9 ]}
في علم النفس الرياضي ، من المهم تحديد تصنيفات الأفراد لمجموعات من الأشياء وفقًا لمعيار محدد، مثل تفضيلهم أو إدراكهم للحجم، وذلك بناءً على مقارنات ثنائية بين جميع أزواج الأشياء. توفر مجموعة أقواس التغذية الراجعة الدنيا في مخطط البطولة تصنيفًا يتعارض مع أقل عدد ممكن من نتائج المقارنات الثنائية. ^{[ 2 ]}^{[ 10 ]} بدلاً من ذلك، إذا أسفرت هذه المقارنات عن احتمالات مستقلة لكل ترتيب ثنائي، فيمكن الحصول على تقدير الاحتمال الأقصى للتصنيف الإجمالي عن طريق تحويل هذه الاحتمالات إلى احتمالات لوغاريتمية وإيجاد مجموعة أقواس التغذية الراجعة ذات الوزن الأدنى في البطولة الناتجة. ^{[ 2 ]}^{[ 3 ]}
يمكن استخدام نفس ترتيب الاحتمال الأقصى للتسلسل ، وهي مشكلة في الإحصاء وتحليل البيانات الاستكشافي تتمثل في ترتيب العناصر في ترتيب خطي، في الحالات التي تتوفر فيها بيانات توفر مقارنات ثنائية بين العناصر. ^{[ 3 ]}^{[ 11 ]}^{[ 12 ]}
في نظام التصويت الترتيبي ، يمكن وصف طريقة كيميني-يونغ بأنها تسعى إلى إيجاد ترتيب يقلل من مجموع عدد الناخبين الذين يفضلون الترتيب المعاكس لكل زوج من المرشحين. ^{[ 13 ]} ويمكن صياغة هذه المسألة وحلها كمسألة مجموعة أقواس التغذية الراجعة ذات الوزن الأدنى، حيث تمثل الرؤوس المرشحين، وتتجه الحواف لتمثيل الفائز في كل منافسة مباشرة، وتمثل تكلفة كل حافة عدد الناخبين الذين سيشعرون بالاستياء من منح ترتيب أعلى للخاسر في المنافسة المباشرة. ^{[ 14 ]}

Another early application of feedback arc sets concerned the design of sequential logic circuits, in which signals can propagate in cycles through the circuit instead of always progressing from inputs to outputs. In such circuits, a minimum feedback arc set characterizes the number of points at which amplification is necessary to allow the signals to propagate without loss of information.^[15] In synchronous circuits made from asynchronous components, synchronization can be achieved by placing clocked gates on the edges of a feedback arc set.^[16] Additionally, cutting a circuit on a feedback arc a set reduces the remaining circuit to combinational logic, simplifying its analysis, and the size of the feedback arc set controls how much additional analysis is needed to understand the behavior of the circuit across the cut.^[15] Similarly, in process flowsheeting in chemical engineering, breaking edges of a process flow diagram on a feedback arc set, and guessing or trying all possibilities for the values on those edges, allows the rest of the process to be analyzed in a systematic way because of its acyclicity. In this application, the idea of breaking edges in this way is called "tearing".^[17]

In layered graph drawing, the vertices of a given directed graph are partitioned into an ordered sequence of subsets (the layers of the drawing), and each subset is placed along a horizontal line of this drawing, with the edges extending upwards and downwards between these layers. In this type of drawing, it is desirable for most or all of the edges to be oriented consistently downwards, rather than mixing upwards and downwards edges, in order for the reachability relations in the drawing to be more visually apparent. This is achieved by finding a minimum or minimal feedback arc set, reversing the edges in that set, and then choosing the partition into layers in a way that is consistent with a topological order of the resulting acyclic graph.^[18]^[19] Feedback arc sets have also been used for a different subproblem of layered graph drawing, the ordering of vertices within consecutive pairs of layers.^[20]

في حلّ حالات الجمود في أنظمة التشغيل ، يمكن نمذجة مشكلة إزالة أقل عدد ممكن من التبعيات لكسر الجمود على أنها إيجاد مجموعة أقواس التغذية الراجعة الدنيا. ^{[ 21 ]}^{[ 22 ]} ومع ذلك، ونظرًا للصعوبة الحسابية لإيجاد هذه المجموعة، والحاجة إلى السرعة ضمن مكونات نظام التشغيل، غالبًا ما تُستخدم الطرق الاستدلالية بدلًا من الخوارزميات الدقيقة في هذا التطبيق. ^{[ 22 ]}

الخوارزميات

المكافئات

تُعتبر مجموعة أقواس التغذية الراجعة الدنيا والرسم البياني الفرعي غير الدوري الأقصى متكافئين لأغراض التحسين الدقيق، حيث أن أحدهما مجموعة مكملة للآخر. ومع ذلك، يختلفان في حالة التعقيد المُعامل والتقريب، لأن التحليل المستخدم في هذا النوع من الخوارزميات يعتمد على حجم الحل وليس فقط على حجم الرسم البياني المُدخل، كما أن مجموعة أقواس التغذية الراجعة الدنيا والرسم البياني الفرعي غير الدوري الأقصى لهما أحجام مختلفة. ^{[ 23 ]}

مجموعة أقواس التغذية الراجعة لرسم بياني معين $G$ وهو نفسه مجموعة رؤوس التغذية الراجعة في الرسم البياني الخطي الموجه لـ $G$ هنا ، تُعرَّف مجموعة رؤوس التغذية الراجعة بشكل مشابه لمجموعة أقواس التغذية الراجعة، باعتبارها مجموعة فرعية من رؤوس الرسم البياني التي يؤدي حذفها إلى إزالة جميع الدورات. الرسم البياني الخطي للرسم البياني الموجه $G$ يحتوي على رأس لكل حافة من $G$ وحافة لكل مسار ذي حافتين في $G$ في الاتجاه الآخر ، مجموعة رؤوس التغذية الراجعة الدنيا لرسم بياني معين $G$ يمكن الحصول على ذلك من حل مسألة مجموعة أقواس التغذية الراجعة الدنيا على الرسم البياني الذي تم الحصول عليه عن طريق تقسيم كل رأس من رؤوس $G$ إلى رأسين، أحدهما للحواف الواردة والآخر للحواف الصادرة. تسمح هذه التحويلات بتحويل الخوارزميات الدقيقة لمجموعات أقواس التغذية الراجعة ومجموعات رؤوس التغذية الراجعة إلى بعضها البعض، مع ترجمة مناسبة لحدود تعقيدها. ومع ذلك، لا يحافظ هذا التحويل على جودة التقريب لمسألة الرسم البياني الفرعي غير الدوري الأقصى. ^{[ 21 ]}^{[ 24 ]}

رسم بياني موجه بثلاثة مكونات متصلة بقوة ، يمكن تقسيم أقصاها إلى نصفين عند رأس المفصل. $d$ إلى مكونين ثنائيي الاتصال ، كل منهما عبارة عن دورة من رأسين. يمكن حل مشكلة مجموعة أقواس التغذية الراجعة بشكل منفصل في كل مكون متصل بقوة، وفي كل مكون ثنائي الاتصال من مكون متصل بقوة.

{\displaystyle d} — رسم بياني موجه بثلاثة مكونات متصلة بقوة ، يمكن تقسيم أقصاها إلى نصفين عند رأس المفصل. $d$ إلى مكونين ثنائيي الاتصال ، كل منهما عبارة عن دورة من رأسين. يمكن حل مشكلة مجموعة أقواس التغذية الراجعة بشكل منفصل في كل مكون متصل بقوة، وفي كل مكون ثنائي الاتصال من مكون متصل بقوة.

في كلٍّ من الحلول الدقيقة والتقريبية لمسألة مجموعة أقواس التغذية الراجعة، يكفي حلّ كل مكون متصل بقوة من الرسم البياني المعطى على حدة، ثم تقسيم هذه المكونات المتصلة بقوة إلى مكوناتها ثنائية الاتصال بفصلها عند رؤوس التمفصل. لا يؤثر اختيار الحل في أيٍّ من هذه المسائل الفرعية على المسائل الأخرى، والحواف التي لا تظهر في أيٍّ من هذه المكونات لا تُفيد في إدراجها في مجموعة أقواس التغذية الراجعة. ^{[ 25 ]} عندما يُمكن فصل أحد هذه المكونات إلى رسمين بيانيين فرعيين منفصلين بإزالة رأسين، يُمكن تطبيق تجزئة أكثر تعقيدًا، مما يسمح بتقسيم المسألة إلى مسائل فرعية مُشتقة من المكونات ثلاثية الاتصال لمكوناتها المتصلة بقوة. ^{[ 26 ]}

بالضبط

إحدى طرق إيجاد مجموعة أقواس التغذية الراجعة الدنيا هي البحث عن ترتيب للرؤوس بحيث يكون أقل عدد ممكن من الحواف موجهًا من الرؤوس اللاحقة إلى الرؤوس السابقة في هذا الترتيب. ^{[ 27 ]} البحث في جميع تباديل مجموعة أقواس التغذية الراجعة الدنيا. $n$ سيستغرق رسم بياني الرؤوس وقتًا $O(n!)$ لكن طريقة البرمجة الديناميكية القائمة على خوارزمية هيلد-كارب يمكنها إيجاد التبديل الأمثل في وقت $O(n2^{n})$ كما أنها تستخدم مساحة هائلة. ^{[ 28 ]}^{[ 29 ]} يمكن لخوارزمية فرق تسد، التي تختبر جميع تقسيمات الرؤوس إلى مجموعتين فرعيتين متساويتين وتستدعي التكرار داخل كل مجموعة فرعية، أن تحل المشكلة في وقت $O(4^{n}/{\sqrt {n}})$ باستخدام الفضاء متعدد الحدود . ^{[ 29 ]}

في التعقيد المُعَلم ، لا يُقاس زمن الخوارزميات بحجم الرسم البياني المُدخل فحسب، بل يُقاس أيضًا بمعامل منفصل للرسم البياني. على وجه الخصوص، في مسألة مجموعة أقواس التغذية الراجعة الدنيا، يُعدّ ما يُسمى بالمعامل الطبيعي هو حجم مجموعة أقواس التغذية الراجعة الدنيا. على الرسوم البيانية ذات $n$ الرؤوس، مع المعامل الطبيعي $k$ يمكن حل مشكلة مجموعة أقواس التغذية الراجعة في الوقت المناسب $O(n^{4}4^{k}k^{3}k!)$ وذلك بتحويلها إلى مسألة مجموعة رؤوس تغذية راجعة مكافئة وتطبيق خوارزمية مجموعة رؤوس تغذية راجعة مُعَلمة. لأن أس $n$ الثابت في هذه الخوارزمية $4$ ، بغض النظر عن $k$ ويُقال إن هذه الخوارزمية قابلة للمعالجة باستخدام معلمات ثابتة. ^{[ 30 ]}

تمت دراسة معايير أخرى غير المعيار الطبيعي. يمكن لخوارزمية قابلة للمعالجة ذات معايير ثابتة باستخدام البرمجة الديناميكية إيجاد مجموعات أقواس التغذية الراجعة الدنيا في وقت $O(2^{r}m^{4}\log m)$ ، أين $r$ يمثل رتبة الدائرة للرسم البياني غير الموجه الأساسي. رتبة الدائرة هي نظير غير موجه لمجموعة أقواس التغذية الراجعة، وهي الحد الأدنى لعدد الحواف التي يجب إزالتها من رسم بياني متصل لتقليله إلى شجرة ممتدة ؛ وهي أسهل بكثير في الحساب من الحد الأدنى لمجموعة أقواس التغذية الراجعة. ^{[ 24 ]} بالنسبة للرسوم البيانية ذات عرض الشجرة $t$ يمكن للبرمجة الديناميكية على تحليل شجري للرسم البياني إيجاد مجموعة أقواس التغذية الراجعة الدنيا في وقت متعدد الحدود بالنسبة لحجم الرسم البياني وأُسّي بالنسبة لـ $O(t\log t)$ في ظل فرضية الزمن الأسي ، لا يوجد اعتماد أفضل على $t$ من الممكن. ^{[ 31 ]}

بدلاً من تقليل حجم مجموعة أقواس التغذية الراجعة، بحث الباحثون أيضاً في تقليل الحد الأقصى لعدد الحواف التي يمكن إزالتها من أي رأس. يمكن حل هذا النوع من المشكلة في زمن خطي . ^{[ 32 ]} يمكن سرد جميع مجموعات أقواس التغذية الراجعة الدنيا بواسطة خوارزمية ذات تأخير متعدد الحدود لكل مجموعة. ^{[ 33 ]}

تقريبي

مشكلة لم تُحل في الرياضيات

هل توجد خوارزمية تقريبية لمشكلة مجموعة أقواس التغذية الراجعة بنسبة تقريب ثابتة؟

تتميز أفضل خوارزمية تقريبية معروفة ذات زمن متعدد الحدود لمجموعة أقواس التغذية الراجعة بنسبة تقريب غير ثابتة $O(\log n\log \log n)$ هذا يعني أن حجم مجموعة أقواس التغذية الراجعة التي يتم العثور عليها لا يتجاوز هذا العامل من الحجم الأمثل. ^{[ 21 ]} ولا تزال مسألة تحديد ما إذا كانت مجموعة أقواس التغذية الراجعة تمتلك خوارزمية تقريب بنسبة ثابتة، أو ما إذا كانت هناك حاجة إلى نسبة غير ثابتة، مسألة مفتوحة. ^{[ 34 ]}

تتميز مسألة إيجاد أكبر رسم بياني فرعي غير دوري بخوارزمية تقريب سهلة تحقق نسبة تقريب تبلغ ${\tfrac {1}{2}}$ :

حدد ترتيبًا عشوائيًا للرؤوس
قسّم الحواف إلى رسمين فرعيين غير دوريين، أحدهما يتكون من الحواف الموجهة بشكل متسق مع الترتيب، والآخر يتكون من الحواف الموجهة بشكل معاكس للترتيب.
أعد الرسم البياني الفرعي الأكبر من بين الرسمين.

يمكن تحسين ذلك باستخدام خوارزمية جشعة لاختيار الترتيب. تجد هذه الخوارزمية رأسًا تتباعد فيه أعداد الحواف الداخلة والخارجة قدر الإمكان، ثم تحذفه، وترتب الرسم البياني المتبقي بشكل متكرر، ثم تضع الرأس المحذوف في أحد طرفي الترتيب الناتج. بالنسبة للرسوم البيانية ذات $m$ الحواف و $n$ ينتج عن ذلك رسم بياني فرعي غير دوري يحتوي على رؤوس $m/2+n/6$ الحواف، في زمن خطي، مما يعطي نسبة تقريبية لـ ${\tfrac {1}{2}}+\أوميغا (n/m)$ [ ³⁵^] هناك خوارزمية تقريب أخرى أكثر تعقيدًا، ذات زمن متعدد الحدود، تُطبق على الرسوم البيانية ذات الدرجة القصوى ^. $\Delta$ ويجد رسمًا بيانيًا فرعيًا غير دوري مع $m/2+\Omega (m/{\sqrt {\Delta }})$ الحواف، مما يعطي نسبة تقريبية على النحو التالي: ${\tfrac {1}{2}}+\أوميغا (1/{\sqrt {\Delta }})$ [ ³⁶^]^[³⁷^] عندما $\Delta =3$ نسبة التقريب $8/9$ يمكن تحقيق ذلك. ^{[ 38 ]}

المدخلات المقيدة

في الرسوم البيانية المستوية الموجهة ، تُعدّ مسألة مجموعة أقواس التغذية الراجعة ثنائية لمسألة تقليص مجموعة من الحواف ( مجموعة ثنائية ) لجعل الرسم البياني الناتج متصلاً بقوة . ^{[ 39 ]} هذه المسألة الثنائية قابلة للحل في زمن متعدد الحدود، ^{[ 40 ]} وبالتالي فإن مسألة مجموعة أقواس التغذية الراجعة الدنيا المستوية قابلة للحل أيضًا. ^{[ 41 ]}^{[ 40 ]} ويمكن حلها في زمن $O(n^{5/2}\log n)$ [ ^{42 ]} يمكن حل نسخة موزونة من المشكلة ^في وقت $O(n^{3})$ [ ³⁹^] أو عندما تكون الأوزان أعدادًا صحيحة موجبة لا تتجاوز عددًا معينًا ^. $N$ مع مرور الوقت $O(n^{5/2}\log nN)$ [ ⁴²^] يمكن توسيع نطاق هذه الخوارزميات المستوية لتشمل الرسوم البيانية التي لا تحتوي على رسم بياني للمنفعة ^. $K_{3,3}$ باعتبارها مخططًا فرعيًا ، بالاستفادة من حقيقة أن المكونات ثلاثية الاتصال لهذه المخططات إما مستوية أو ذات حجم محدود. ^{[ 26 ]} كما تم تعميم المخططات المستوية بطريقة مختلفة إلى فئة من المخططات الموجهة تسمى المخططات الموجهة ضعيفة عدم الدورية ، والتي تُعرَّف بتكامل متعدد السطوح معين مرتبط بمجموعات أقواس التغذية الراجعة الخاصة بها . كل مخطط موجه مستوٍ هو ضعيف عدم الدورية بهذا المعنى، ويمكن حل مشكلة مجموعة أقواس التغذية الراجعة في وقت متعدد الحدود لجميع المخططات الموجهة ضعيفة عدم الدورية. ^{[ 43 ]}

تُعدّ مخططات التدفق القابلة للاختزال فئة أخرى من المخططات الموجهة التي يمكن حلّ مسألة مجموعة أقواس التغذية الراجعة عليها في وقت متعدد الحدود. تصف هذه المخططات تدفق التحكم في البرامج المهيكلة للعديد من لغات البرمجة. على الرغم من أن البرامج المهيكلة غالبًا ما تُنتج مخططات تدفق موجهة مستوية، إلا أن تعريف قابلية الاختزال لا يشترط أن يكون المخطط مستويًا. ^{[ 44 ]}

عندما تُحصر مسألة مجموعة أقواس التغذية الراجعة الدنيا في البطولات ، فإنها تمتلك مخطط تقريبي متعدد الحدود ، والذي يُعمم إلى نسخة موزونة من المسألة. ^{[ 45 ]} كما تُعرف خوارزمية مُعاملة شبه أسية لمجموعات أقواس التغذية الراجعة الموزونة في البطولات. ^{[ 14 ]} وتمتلك مسألة الرسم البياني الفرعي الأقصى غير الدوري للرسوم البيانية الكثيفة أيضًا مخطط تقريبي متعدد الحدود. وتتمثل أفكارها الرئيسية في تطبيق التقريب العشوائي على استرخاء البرمجة الخطية للمسألة، وإزالة العشوائية من الخوارزمية الناتجة باستخدام المسارات على الرسوم البيانية الموسعة . ^{[ 34 ]}^{[ 46 ]}

صلابة

صعوبة NP

من أجل تطبيق نظرية اكتمال NP على مجموعة أقواس التغذية الراجعة الدنيا، من الضروري تعديل المشكلة من كونها مشكلة تحسين (كم عدد الحواف التي يمكن إزالتها لكسر جميع الحلقات) إلى نسخة قرار مكافئة ، بإجابة نعم أو لا (هل من الممكن إزالة $k$ (الحواف). وبالتالي، فإن نسخة القرار من مشكلة مجموعة أقواس التغذية الراجعة تأخذ كمدخل كلاً من الرسم البياني الموجه ورقمًا . $k$ يسأل عما إذا كان من الممكن كسر جميع الدورات بإزالة ما لا يزيد عن $k$ الحواف، أو ما يعادلها، ما إذا كان هناك رسم بياني فرعي غير دوري يحتوي على الأقل $|E(G)|-k$ الحواف. هذه المسألة من فئة NP-كاملة ، مما يعني أنه لا يُتوقع أن يكون لها، ولا لمسألة التحسين، خوارزميات ذات زمن متعدد الحدود. كانت هذه المسألة إحدى مسائل ريتشارد إم. كارب الأصلية الـ 21 من فئة NP-كاملة ؛ وقد أثبت كارب ويوجين لولر اكتمالها من فئة NP-كاملة من خلال إظهار أن مدخلات مسألة صعبة أخرى، وهي مسألة تغطية الرؤوس ، يمكن تحويلها ("اختزالها") إلى مدخلات مكافئة لمسألة قرار مجموعة أقواس التغذية الراجعة. ^{[ 47 ]}^{[ 48 ]}

قد تصبح بعض المسائل المصنفة ضمن فئة NP-complete أسهل عند حصر مدخلاتها في حالات خاصة. ولكن بالنسبة لأهم حالة خاصة من مسائل مجموعة أقواس التغذية الراجعة، وهي حالة البطولات، تظل المسألة مصنفة ضمن فئة NP-complete. ^{[ 49 ]}^{[ 50 ]}

عدم التقريب

تُعرَّف فئة التعقيد APX بأنها تتألف من مسائل التحسين التي تمتلك خوارزمية تقريبية ذات زمن متعدد الحدود تحقق نسبة تقريب ثابتة . على الرغم من عدم وجود تقريبات مماثلة لمسألة مجموعة أقواس التغذية الراجعة، إلا أن هذه المسألة تُعرف بأنها صعبة في فئة APX ، مما يعني أنه يمكن استخدام التقريبات الدقيقة لها لتحقيق تقريبات مماثلة في الدقة لجميع المسائل الأخرى في APX. ونتيجةً لإثبات صعوبتها، فإنه ما لم تكن P = NP ، لا توجد نسبة تقريبية ذات زمن متعدد الحدود أفضل من 1.3606. وهذا هو نفس الحد الأدنى لصعوبة التقريب المعروف لمسألة تغطية الرؤوس، ويستخدم البرهان اختزال كارب-لور من تغطية الرؤوس إلى مجموعة أقواس التغذية الراجعة، مما يحافظ على جودة التقريبات. ^{[ 34 ]}^{[ 51 ]}^{[ 52 ]}^{[ 53 ]} وباختزال مختلف، فإن مسألة الرسم البياني الفرعي الأقصى غير الدوري هي أيضًا مسألة صعبة من نوع APX، وصعبة من نوع NP لتقريبها ضمن عامل 65/66 من الحل الأمثل. ^{[ 38 ]}

تمت دراسة صعوبة تقريب هذه المسائل أيضًا في ظل افتراضات صعوبة حسابية غير مثبتة ، وهي افتراضات قياسية في نظرية التعقيد الحسابي، ولكنها أقوى من P ≠ NP. إذا كانت فرضية الألعاب الفريدة صحيحة، فإن مسألة مجموعة أقواس التغذية الراجعة الدنيا يصعب تقريبها في وقت متعدد الحدود ضمن أي عامل ثابت، كما يصعب تقريب مسألة مجموعة أقواس التغذية الراجعة القصوى ضمن عامل من ${\tfrac {1}{2}}+\varepsilon$ لكل $\varepsilon >0$ [ ⁵⁴^]^إذا تجاوز وقت التقريب متعدد الحدود، وكانت فرضية الوقت الأسي صحيحة، فإنه لكل $\varepsilon >0$ لا يوجد تقريب لمجموعة أقواس التغذية الراجعة الدنيا ضمن عامل معين. ${\tfrac {7}{6}}-\varepsilon$ يمكن حساب ذلك في الحد الزمني شبه الأسي $O(2^{n^{1-\varepsilon }})$ [ ⁵⁵^]

نظرية

في الرسوم البيانية الموجهة المستوية، تخضع مسألة مجموعة أقواس التغذية الراجعة لنظرية الحد الأدنى والحد الأقصى : حيث يساوي الحد الأدنى لحجم مجموعة أقواس التغذية الراجعة الحد الأقصى لعدد الدورات الموجهة غير المتداخلة التي يمكن إيجادها في الرسم البياني. ^{[ 41 ]}^{[ 56 ]} لا ينطبق هذا على بعض الرسوم البيانية الأخرى؛ فعلى سبيل المثال، يوضح الرسم التوضيحي الأول نسخة موجهة من الرسم البياني غير المستوي. $K_{3,3}$ حيث يكون الحد الأدنى لحجم مجموعة قوس التغذية الراجعة اثنين، بينما يكون الحد الأقصى لعدد الدورات الموجهة المنفصلة عن الحواف واحدًا فقط.

لكل رسم بياني للبطولة مسار هاميلتوني ، وتتوافق هذه المسارات بشكل مباشر مع مجموعات أقواس التغذية الراجعة الدنيا، المنفصلة عن المسار المقابل. يُحدد المسار الهاميلتوني لمجموعة أقواس التغذية الراجعة بعكس أقواسها وإيجاد ترتيب طوبولوجي للبطولة غير الدورية الناتجة. يجب أن يكون كل زوج متتالٍ من هذا الترتيب منفصلاً عن مجموعات أقواس التغذية الراجعة، وإلا فإنه يمكن إيجاد مجموعة أقواس تغذية راجعة أصغر بعكس هذا الزوج. بالتالي، يُعطي هذا الترتيب مسارًا عبر أقواس البطولة الأصلية، يغطي جميع الرؤوس. في المقابل، من أي مسار هاميلتوني، تُشكل مجموعة الحواف التي تربط الرؤوس اللاحقة في المسار بالرؤوس السابقة مجموعة أقواس تغذية راجعة. وهي دنيا، لأن كل حافة من حوافها تنتمي إلى دورة ذات حواف مسار هاميلتوني منفصلة عن جميع الدورات المماثلة الأخرى. ^{[ 57 ]} في البطولة، قد يكون كل من مجموعة أقواس التغذية الراجعة الدنيا والرسم البياني الفرعي غير الدوري الأقصى قريبين من نصف الحواف. وبشكل أدق، يحتوي كل رسم بياني للبطولة على مجموعة أقواس تغذية راجعة بحجم ${\tbinom {n}{2}}/2-\أوميغا (n^{3/2})$ وتتطلب بعض البطولات حجمًا معينًا . ${\tbinom {n}{2}}/2-O(n^{3/2})$ [ ⁵⁸^] بالنسبة لجميع البطولات تقريبًا ^، يكون الحجم على الأقل ${\tbinom {n}{2}}/2-1.73n^{3/2}$ [ ^{59 ]} كل ^رسم بياني موجه غير دوري $D$ يمكن تضمينها كرسم بياني فرعي لرسم بياني أكبر للبطولة، بطريقة تجعل $D$ يمثل هذا الحد الأدنى الفريد لمجموعة أقواس التغذية الراجعة في البطولة. وقد تم تحديد حجم هذه البطولة على أنه "عدد الانعكاسات" لـ $D$ ويكون أكبر ما يمكن بين الرسوم البيانية الموجهة غير الدورية التي لها نفس عدد الرؤوس عندما $D$ هي نفسها بطولة (غير دورية). ^{[ 60 ]}^{[ 61 ]}

يحتوي الرسم البياني الموجه على مسار أويلر عندما يكون متصلاً بقوة ويكون لكل رأس عدد متساوٍ من الحواف الداخلة والخارجة. بالنسبة لمثل هذا الرسم البياني، مع $m$ الحواف و $n$ بالنسبة للرؤوس، يكون حجم مجموعة أقواس التغذية الراجعة الدنيا دائمًا على الأقل $(m^{2}+mn)/2n^{2}$ يوجد عدد لا نهائي من الرسوم البيانية الموجهة وفقًا لنظرية أويلر التي يكون هذا الحد دقيقًا بالنسبة لها. [ ^{62 ] إذا} كان الرسم البياني الموجه يحتوي على $n$ إذا كان عدد الرؤوس ثلاثة على الأكثر، فإن مجموعة أقواس التغذية الراجعة ستكون على الأكثر $n/3$ الحواف، وبعض الرسوم البيانية تتطلب هذا العدد. إذا كان الرسم البياني الموجه يحتوي على $m$ إذا كان عدد الحواف أربعة على الأكثر لكل رأس، فإن مجموعة أقواس التغذية الراجعة ستكون على الأكثر $m/3$ الحواف، وبعض الرسوم البيانية تتطلب هذا العدد. ^{[ 63 ]}

مراجع

↑ "القرعة الرئيسية - رجال" ، ريو 2016 ، الاتحاد الدولي للكرة الطائرة ، مؤرشف من الأصل بتاريخ 23 ديسمبر 2016 ، تم الاطلاع عليه بتاريخ 14 نوفمبر 2021
1 2 3 هوبرت، لورانس (1976)، "التسلسل باستخدام مقاييس التقارب غير المتماثلة"، المجلة البريطانية لعلم النفس الرياضي والإحصائي ، 29 (1): 32-52 ، doi : 10.1111/j.2044-8317.1976.tb00701.x ، MR 0429180
1 2 3 ريماج، راسل الابن؛ طومسون، دبليو إيه الابن (1966)، "تصنيفات المقارنة الزوجية ذات الاحتمالية القصوى"، بيومتريكا ، 53 ( 1-2 ): 143-149 ، doi : 10.1093/biomet/53.1-2.143 ، JSTOR 2334060 ، MR 0196854 ، PMID 5964054
↑ جودارد، ستيفن ت. (1983)، "التصنيف في البطولات واتخاذ القرارات الجماعية"، مجلة علوم الإدارة ، 29 (12): 1384-1392 ، doi : 10.1287/mnsc.29.12.1384 ، MR 0809110 لاحظ أن الخوارزمية التي اقترحها جودارد لإيجاد تصنيفات الحد الأدنى من الانتهاكات غير صحيحة
↑ فازيري، باباك؛ دابادغاو، شوناك؛ ييه، يوهويرن ؛ مورين، توماس ل. (يناير 2018)، "خصائص أساليب تصنيف الرياضة" (ملف PDF) ، مجلة جمعية بحوث العمليات ، 69 (5): 776-787 ، doi : 10.1057/s41274-017-0266-8 ، S2CID 51887586
↑ كوبرسميث، دون ؛ فليشر، ليزا ك.؛ روردا، أتري (2010)، "الترتيب حسب عدد مرات الفوز المرجحة يعطي تصنيفًا جيدًا للبطولات المرجحة"، معاملات ACM في الخوارزميات ، 6 (3): A55:1–A55:13، doi : 10.1145/1798596.1798608 ، MR 2682624 ، S2CID 18416
↑ سيفارث، روبرت م. (نوفمبر 1976)، "العلاقات الاجتماعية بين إناث البابون البالغات"، سلوك الحيوان ، 24 (4): 917-938 ، doi : 10.1016/s0003-3472(76)80022-x ، S2CID 54284406
↑ إستيب، دي كيو؛ كرويل-ديفيس، إس إل؛ إيرل-كوستيلو، إس-إيه؛ بيتي، إس إيه (يناير 1993)، "تغيرات في السلوك الاجتماعي لأفراس الخيول الثقيلة (Equus caballus) بالتزامن مع الولادة"، مجلة علم سلوك الحيوان التطبيقي ، 35 (3): 199-213 ، doi : 10.1016/0168-1591(93)90137-e
↑ إيكوورت، جورج سي. (أبريل 2019)، "الهيمنة في الصرصور (نوفويتا)"، سلوك الحشرات ، مطبعة سي آر سي، ص 120-126 ، doi : 10.1201/9780429049262-18 ، ISBN 978-0-429-04926-2، S2CID 203898549
↑ سلاتر، باتريك (1961)، "التناقضات في جدول المقارنات الزوجية"، Biometrika ، 48 ( 3-4 ): 303-312 ، doi : 10.1093/biomet/48.3-4.303 ، JSTOR 2332752
↑ برونك، إتش دي (1960)، "النماذج الرياضية للترتيب من المقارنات الزوجية"، مجلة الجمعية الإحصائية الأمريكية ، 55 (291): 503-520 ، doi : 10.2307/2281911 ، JSTOR 2281911 ، MR 0115242 نُشرت في شكل أولي كوثيقة ASTIA رقم AD 206 573، القوات الجوية الأمريكية، مكتب البحوث العلمية، نوفمبر 1958، hdl : 2027/mdp.39015095254010
↑ تومسون، دبليو إيه جونيور؛ ريماج، راسل جونيور (1964)، "التصنيفات من المقارنات الزوجية"، حوليات الإحصاء الرياضي ، 35 (2): 739-747 ، doi : 10.1214/aoms/1177703572 ، JSTOR 2238526 ، MR 0161419
↑ كيميني، جون ج. (خريف 1959)، "الرياضيات بدون أرقام"، ديدالوس ، 88 (4): 577-591 ، JSTOR 20026529
1 2 كاربينسكي، ماريك ؛ شودي، وارن (2010)، "خوارزميات أسرع لبطولة مجموعة قوس التغذية الراجعة، وتجميع رتبة كيميني، وبطولة الوساطة"، في تشيونغ، أوتفريد ؛ تشوا، كيونغ يونغ؛ بارك، كونسو (محررون)، الخوارزميات والحوسبة - الندوة الدولية الحادية والعشرون، ISAAC 2010، جزيرة جيجو، كوريا، 15-17 ديسمبر 2010، وقائع، الجزء الأول ، سلسلة محاضرات في علوم الحاسوب، المجلد 6506، سبرينغر، الصفحات 3-14 ، arXiv : 1006.4396 ، doi : 10.1007/978-3-642-17517-6_3 ، ISBN 978-3-642-17516-9، S2CID 16512997
1 2 أونغر، ستيفن هـ. (26 أبريل 1957)، دراسة لشبكات التغذية الراجعة المنطقية غير المتزامنة ، التقارير الفنية، المجلد 320، معهد ماساتشوستس للتكنولوجيا، مختبر أبحاث الإلكترونيات، hdl : 1721.1/4763
↑ فيهر، جون ر.؛ جوردان، هاري ف. (ديسمبر 1995)، "وضع بوابات الساعة في دوائر الإلكترونيات الضوئية بتقنية زمن الرحلة"، البصريات التطبيقية ، 34 (35): 8125-8136 ، Bibcode : 1995ApOpt..34.8125F ، doi : 10.1364/ao.34.008125 ، PMID 21068927
↑ روزن، إدوارد م.؛ هينلي، إرنست ج. (صيف 1968)، "القياس الكمي الجديد" ، تعليم الهندسة الكيميائية ، 2 (3): 120-125 ، مؤرشف من الأصل في 2021-08-02 ، تم استرجاعه في 2021-08-02
↑ دي باتيستا، جوزيبي؛ إيدز، بيتر ؛ تاماسيا، روبرتو ؛ توليس، يوانيس ج. (1998)، "الرسومات الطبقية للرسوم البيانية الموجهة"، رسم الرسوم البيانية: خوارزميات لتصور الرسوم البيانية ، برنتيس هول ، ص 265-302 ، ISBN 978-0-13-301615-4
↑ باسترت، أوليفر؛ ماتوسزوسكي، كريستيان (2001)، "الرسومات الطبقية للرسوم البيانية الموجهة"، في كوفمان، مايكل؛ فاغنر، دوروثيا (محرران)، رسم الرسوم البيانية: الأساليب والنماذج ، سلسلة محاضرات في علوم الحاسوب، المجلد 2025، سبرينغر-فيرلاغ، الصفحات 87-120 ، doi : 10.1007/3-540-44969-8_5 ، ISBN 978-3-540-42062-0
↑ ديميتريسكو، كاميل؛ فينوتشي، إيرين (2001)، "كسر الحلقات "الصحيحة" والحصول على الرسم "الأفضل"، مجلة ACM للخوارزميات التجريبية ، 6 : 171-182 ، MR 2027115
1 2 3 إيفن، جي.؛ ناور، ج .؛ شيبر، ب .؛ سودان، م. (1998)، "تقريب مجموعات التغذية الراجعة الدنيا والقطع المتعددة في الرسوم البيانية الموجهة"، Algorithmica ، 20 (2): 151-174 ، doi : 10.1007/PL00009191 ، MR 1484534 ، S2CID 2437790
1 2 مينورا، توشيمي (1982)، "إعادة النظر في تجنب حالات الجمود"، مجلة ACM ، 29 (4): 1023-1048 ، doi : 10.1145/322344.322351 ، MR 0674256 ، S2CID 5284738
↑ ميشرا، سوناكا؛ سيكدار، كريباسيندو (2004)، "حول إمكانية تقريب الترتيب الخطي ومسائل التحسين NP ذات الصلة على الرسوم البيانية"، الرياضيات التطبيقية المنفصلة ، 136 ( 2-3 ): 249-269 ، doi : 10.1016/S0166-218X(03)00444-X ، MR 2045215
1 2 هيشت، مايكل (2017)، "تحديدات دقيقة لمجموعات التغذية الراجعة"، نظرية أنظمة الحوسبة ، 62 (5): 1048-1084 ، arXiv : 1702.07612 ، doi : 10.1007/s00224-017-9777-6 ، S2CID 18394348
↑ بارك، س.؛ أكيرز، س.ب. (1992)، "طريقة فعالة لإيجاد مجموعة أقواس التغذية الراجعة الدنيا في الرسوم البيانية الموجهة"، وقائع ندوة IEEE الدولية للدوائر والأنظمة لعام 1992 (ISCAS '92) ، المجلد 4، الصفحات 1863-1866 ، doi : 10.1109/iscas.1992.230449 ، ISBN 0-7803-0593-0، S2CID 122603659
1 2 نوتوف، زئيف؛ بن، ميخال (2000)، "حول التكامل والاستقرار وتكوين حشوات وأغطية الدراجات ثنائية العجلات"، مجلة التحسين التوافقي ، 4 (2): 235-251 ، doi : 10.1023/A:1009802905533 ، MR 1772828 ، S2CID 207632524
↑ يونغر، د. (1963)، "مجموعات أقواس التغذية الراجعة الدنيا للرسم البياني الموجه"، معاملات IEEE في نظرية الدوائر ، 10 (2): 238-245 ، doi : 10.1109/tct.1963.1082116
↑ لولر، إي. (1964)، "تعليق على مجموعات أقواس التغذية الراجعة الدنيا"، معاملات IEEE في نظرية الدوائر ، 11 (2): 296-297 ، doi : 10.1109/tct.1964.1082291
1 2 بودليندر، هانز ل .؛ فومين، فيدور ف.؛ كوستر، آري إم سي إيه؛ كراتش، ديتر؛ ثيليكوس، ديميتريوس م. (2012)، "ملاحظة حول الخوارزميات الدقيقة لمسائل ترتيب الرؤوس على الرسوم البيانية"، نظرية أنظمة الحوسبة ، 50 (3): 420-432 ، doi : 10.1007/s00224-011-9312-0 ، hdl : 1956/4556 ، MR 2885638 ، S2CID 9967521
↑ تشين، جيانر؛ ليو، يانغ؛ لو، سونغجيان؛ أوسوليفان، باري؛ رازغون، إيغور (2008)، "خوارزمية ذات معلمات ثابتة لمسألة مجموعة رؤوس التغذية الراجعة الموجهة"، مجلة ACM ، 55 (5): 1-19 ، doi : 10.1145/1411509.1411511 ، S2CID 1547510
↑ بونامي، مارث؛ كواليك، لوكاس؛ نيدرلوف، يسبر؛ بيليبكزوك، ميخال؛ سوكالا، أركاديوس؛ فروخنا، مارسين (2018)، "حول مجموعة رؤوس التغذية الراجعة الموجهة التي تم تحديدها بواسطة عرض الشجرة"، في براندشتات، أندرياس؛ كولر، إيكهارد؛ مير، كلاوس (محررون)، مفاهيم نظرية الرسم البياني في علوم الحاسوب - ورشة العمل الدولية الرابعة والأربعون، WG 2018، كوتبوس، ألمانيا، 27-29 يونيو 2018، وقائع ، سلسلة محاضرات في علوم الحاسوب، المجلد. 11159، سبرينغر، الصفحات 65-78 ، arXiv : 1707.01470 ، doi : 10.1007/978-3-030-00256-5_6 ، ISBN 978-3-030-00255-8، S2CID 8008855
↑ لين، ليشين؛ ساهني، سرتاج (1989)، "مسائل حذف الحواف العادلة"، معاملات IEEE للحواسيب ، 38 (5): 756-761 ، doi : 10.1109/12.24280 ، MR 0994519
↑ شفيكوفسكي، بينو؛ سبيكنماير، إيوالد (2002)، "حول تعداد جميع الحلول الدنيا لمسائل التغذية الراجعة"، الرياضيات التطبيقية المنفصلة ، 117 ( 1-3 ): 253-265 ، doi : 10.1016/S0166-218X(00)00339-5 ، MR 1881280
1 2 3 كريسينزي، بييرلويجي؛ كان، فيجو؛ هالدورسون، ماغنوس؛ كاربينسكي، ماريك ؛ ووجينجر، جيرهارد (2000)، "مجموعة أقواس التغذية الراجعة الدنيا" ، مجموعة من مسائل التحسين NP ، مؤرشفة من الأصل في 29-07-2021 ، تم استرجاعها في 29-07-2021
↑ إيدز، بيتر ؛ لين، شومين؛ سميث، دبليو إف (1993)، "طريقة استدلالية سريعة وفعالة لمشكلة مجموعة أقواس التغذية الراجعة" ، رسائل معالجة المعلومات ، 47 (6): 319-323 ، doi : 10.1016/0020-0190(93)90079-O ، MR 1256786 ، مؤرشف من الأصل في 22-10-2020 ، تم استرجاعه في 1-08-2021
↑ بيرغر، بوني ؛ شور، بيتر دبليو. (1997)، "حدود دقيقة لمسألة الرسم البياني الفرعي غير الدوري الأقصى"، مجلة الخوارزميات ، 25 (1): 1-18 ، doi : 10.1006/jagm.1997.0864 ، MR 1474592
↑ حسين، رفائيل؛ روبنشتاين، شلومي (1994)، "تقريبات لمسألة الرسم البياني الفرعي غير الدوري الأقصى"، رسائل معالجة المعلومات ، 51 (3): 133-140 ، doi : 10.1016/0020-0190(94)00086-7 ، MR 1290207
1 2 نيومان، ألانثا (يونيو 2000)، تقريب الرسم البياني الفرعي الأقصى غير الدوري (رسالة ماجستير)، معهد ماساتشوستس للتكنولوجيا، hdl : 1721.1/86548 ، كما ورد في غورو سوامي وآخرون (2011)
1 2 جابو، هارولد ن. (1995)، "المراكز، والتمثيلات، والتدفقات شبه المعيارية"، مجلة الخوارزميات ، 18 (3): 586-628 ، doi : 10.1006/jagm.1995.1022 ، MR 1334365
1 2 فرانك، أندراس (1981)، "كيفية إنشاء رسم بياني موجه متصل بقوة"، كومبيناتوريكا ، 1 (2): 145-153 ، doi : 10.1007/BF02579270 ، MR 0625547 ، S2CID 27825518
1 2 لوتشيسي، سي إل؛ يونغر، دي إتش (1978)، "نظرية المينيماكس للرسوم البيانية الموجهة"، مجلة جمعية لندن الرياضية ، السلسلة الثانية، 17 (3): 369-374 ، doi : 10.1112/jlms/s2-17.3.369 ، MR 0500618
1 2 جابو، هارولد ن. (1993)، "إطار عمل لخوارزميات قياس التكلفة لمسائل التدفق شبه المعياري"، الندوة السنوية الرابعة والثلاثون حول أسس علوم الحاسوب، بالو ألتو، كاليفورنيا، الولايات المتحدة الأمريكية، 3-5 نوفمبر 1993 ، جمعية مهندسي الكهرباء والإلكترونيات، ص 449-458 ، doi : 10.1109/SFCS.1993.366842 ، ISBN 0-8186-4370-6، MR 1328441 ، S2CID 32162097
↑ غروتشل، مارتن ؛ يونغر، مايكل؛ راينيلت، غيرهارد (1985)، "حول متعدد السطوح الفرعي غير الدوري"، البرمجة الرياضية ، 33 (1): 28-42 ، doi : 10.1007/BF01582009 ، MR 0809747 ، S2CID 206798683
↑ راماشاندران، فيجايا (1988)، "إيجاد مجموعة أقواس التغذية الراجعة الدنيا في مخططات التدفق القابلة للاختزال"، مجلة الخوارزميات ، 9 (3): 299-313 ، doi : 10.1016/0196-6774(88)90022-3 ، MR 0955140
↑ كينيون-ماثيو، كلير ؛ شودي، وارن (2007)، "كيفية الترتيب بأقل عدد من الأخطاء: خوارزمية تقريبية متعددة الحدود لمجموعة أقواس التغذية الراجعة الموزونة في البطولات"، في جونسون، ديفيد س .؛ فيج، أورييل (محرران)، وقائع الندوة السنوية التاسعة والثلاثين لجمعية آلات الحوسبة حول نظرية الحوسبة، سان دييغو، كاليفورنيا، الولايات المتحدة الأمريكية، 11-13 يونيو 2007 ، الصفحات 95-103 ، doi : 10.1145/1250790.1250806 ، S2CID 9436948 ، ECCC TR06-144 انظر أيضًا النسخة الموسعة للمؤلف. مؤرشفة بتاريخ 15 يناير 2009 في أرشيف الإنترنت (Wayback Machine).
↑ أرورا، سانجيف ؛ فريز، آلان ؛ كابلان، حاييم (2002)، "إجراء تقريب جديد لمسألة التخصيص مع تطبيقات على مسائل ترتيب الرسوم البيانية الكثيفة" ، البرمجة الرياضية ، 92 (1): 1-36 ، doi : 10.1007/s101070100271 ، MR 1892295 ، S2CID 3207086 ، مؤرشف من الأصل في 2021-08-03 ، تم استرجاعه في 2021-08-03
↑ كارب، ريتشارد م. (1972)، "قابلية الاختزال بين المسائل التوافقية"، تعقيد الحسابات الحاسوبية ، وقائع ندوة مركز أبحاث توماس ج. واتسون التابع لشركة آي بي إم، يوركتاون هايتس، نيويورك، نيويورك: بلينوم، ص 85-103
↑ غاري، مايكل ر .؛ جونسون، ديفيد س. (1979)، "A1.1: GT8"، الحواسيب والاستعصاء: دليل لنظرية اكتمال NP ، دبليو إتش فريمان، ص 192، ISBN 0-7167-1045-5
↑ ألون، نوغا (2006)، "بطولات التصنيف"، مجلة SIAM للرياضيات المتقطعة ، 20 (1): 137-142 ، doi : 10.1137/050623905 ، MR 2257251
↑ شاربيت، بيير؛ توماسيه، ستيفان؛ يو، أندرس (2007)، "مشكلة مجموعة أقواس التغذية الراجعة الدنيا هي مسألة صعبة من نوع NP بالنسبة للمسابقات" (ملف PDF) ، التوافقية، الاحتمالات والحوسبة ، 16 (1): 1-4 ، doi : 10.1017/S0963548306007887 ، MR 2282830 ، S2CID 36539840
↑ أوسييلو، ج .؛ داتري، أ.؛ بروتاسي، م. (1980)، "الاختزالات الحافظة للبنية بين مسائل التحسين المحدب"، مجلة علوم الحاسوب والنظم ، 21 (1): 136-153 ، doi : 10.1016/0022-0000(80)90046-X ، MR 0589808
↑ كان، فيجو (1992)، حول إمكانية تقريب مسائل التحسين الكاملة من فئة NP (ملف PDF) (أطروحة دكتوراه)، قسم التحليل العددي وعلوم الحاسوب، المعهد الملكي للتكنولوجيا، ستوكهولم، مؤرشفة (ملف PDF) من الأصل بتاريخ 29-12-2010 ، تم استرجاعها بتاريخ 11-10-2007
↑ دينور، إيريت ؛ صفرا، صموئيل (2005)، "حول صعوبة تقريب غطاء الرؤوس الأدنى" (ملف PDF) ، حوليات الرياضيات ، 162 (1): 439-485 ، doi : 10.4007/annals.2005.162.439 ، مؤرشف (ملف PDF) من الأصل في 20 سبتمبر 2009 ، تم استرجاعه في 29 يوليو 2021 نسخة أولية في دينور، إيريت ؛ صفرا، صموئيل (2002)، "أهمية التحيز"، في ريف، جون هـ. (محرر)، وقائع الندوة السنوية الرابعة والثلاثين لجمعية آلات الحوسبة حول نظرية الحوسبة، 19-21 مايو 2002، مونتريال، كيبيك، كندا ، ص 33-42 ، doi : 10.1145/509907.509915 ، ISBN 1-58113-495-9، S2CID 1235048
↑ غورو سوامي، فينكاتيسان ؛ هاستاد، يوهان ؛ مانوكاران، راجسيكار؛ راغافيندرا، براساد؛ شاريكار، موسى (2011)، "التغلب على الترتيب العشوائي صعب: كل مسألة إرضاء قيود ترتيبية مقاومة للتقريب" (ملف PDF) ، مجلة SIAM للحوسبة ، 40 (3): 878-914 ، doi : 10.1137/090756144 ، MR 2823511 ، مؤرشف (ملف PDF) من الأصل في 31-07-2021 ، تم استرجاعه في 31-07-2021
↑ بونيه، إدوارد؛ باشوس، فانجيليس ث. (2018)، "التخفيف والتقريب شبه الأسي"، أكتا إنفورماتيكا ، 55 (1): 1-15 ، arXiv : 1402.2843 ، doi : 10.1007/s00236-016-0281-2 ، MR 3757549 ، S2CID 3136275
↑ لوفاس، لازلو (1976)، "حول نظريتين من نظريات المينيماكس في الرسم البياني"، مجلة نظرية التوافيق ، السلسلة ب، 21 (2): 96-103 ، doi : 10.1016/0095-8956(76)90049-6 ، MR 0427138
↑ بار-نوي، أموتز؛ ناور، جوزيف (1990)، "الفرز، ومجموعات التغذية الراجعة الدنيا، ومسارات هاميلتون في البطولات"، مجلة SIAM للرياضيات المتقطعة ، 3 (1): 7-20 ، doi : 10.1137/0403002 ، MR 1033709
↑ سبنسر، ج. (1980)، "الترتيب الأمثل للبطولات غير القابلة للترتيب"، مجلة Periodica Mathematica Hungarica ، 11 (2): 131-144 ، doi : 10.1007/BF02017965 ، MR 0573525 ، S2CID 119894999
↑ فرنانديز دي لا فيغا، و. (1983)، "حول الحد الأقصى لعدد عناصر مجموعة متسقة من الأقواس في بطولة عشوائية"، مجلة نظرية التوافيق ، السلسلة ب، 35 (3): 328-332 ، doi : 10.1016/0095-8956(83)90060-6 ، MR 0735201
↑ بارتيليمي، جان بيير؛ هودري، أوليفييه؛ إيزاك، غارث؛ روبرتس، فريد س .؛ تيسمان، باري (1995)، "عدد الانعكاس للرسم البياني الموجه"، الرياضيات التطبيقية المنفصلة ، 60 ( 1-3 ): 39-76 ، doi : 10.1016/0166-218X(94)00042-C ، MR 1339075
↑ إيزاك، غارث؛ نارايان، دارين أ. (2004)، "تصنيف البطولات التي تحتوي على بطولة غير دورية كمجموعة أقواس تغذية راجعة دنيا" ، رسائل معالجة المعلومات ، 92 (3): 107-111 ، doi : 10.1016/j.ipl.2004.07.001 ، MR 2095357
↑ هوانغ، هاو؛ ما، جي؛ شابيرا، آصف؛ سوداكوف، بيني ؛ يوستر، رافائيل (2013)، "مجموعات أقواس التغذية الراجعة الكبيرة، والرسوم البيانية الفرعية ذات الدرجة الدنيا العالية، والدورات الطويلة في الرسوم البيانية الموجهة الأويلرية"، التوافقية، الاحتمالات والحوسبة ، 22 (6): 859-873 ، arXiv : 1202.2602 ، doi : 10.1017/S0963548313000394 ، hdl : 20.500.11850/73894 ، MR 3111546 ، S2CID 7967738
^ هاناور، كاثرين. براندنبورغ، فرانز جوزيف؛ أوير، كريستوفر (2013)، “حدود عليا مشددة للحد الأدنى من مجموعات ردود الفعل من الرسوم البيانية العادية”، في أندرياس براندستات؛ يانسن، كلاوس؛ Reischuk, Rüdiger (eds.)، المفاهيم النظرية للرسم البياني في علوم الكمبيوتر - ورشة العمل الدولية التاسعة والثلاثين، WG 2013، لوبيك، ألمانيا، 19-21 يونيو 2013، أوراق منقحة ، ملاحظات محاضرة في علوم الكمبيوتر، المجلد. 8165، سبرينغر، الصفحات من 298 إلى 309، دوى : 10.1007/978-3-642-45043-3_26 ، ISBN 978-3-642-45042-6MR 3139198

[fivb-1] "القرعة الرئيسية - رجال" ، ريو 2016 ، الاتحاد الدولي للكرة الطائرة ، مؤرشف من الأصل بتاريخ 23 ديسمبر 2016 ، تم الاطلاع عليه بتاريخ 14 نوفمبر 2021

[hubert-2] 1 2 3 هوبرت، لورانس (1976)، "التسلسل باستخدام مقاييس التقارب غير المتماثلة"، المجلة البريطانية لعلم النفس الرياضي والإحصائي ، 29 (1): 32-52 ، doi : 10.1111/j.2044-8317.1976.tb00701.x ، MR 0429180

[rt66-3] 1 2 3 ريماج، راسل الابن؛ طومسون، دبليو إيه الابن (1966)، "تصنيفات المقارنة الزوجية ذات الاحتمالية القصوى"، بيومتريكا ، 53 ( 1-2 ): 143-149 ، doi : 10.1093/biomet/53.1-2.143 ، JSTOR 2334060 ، MR 0196854 ، PMID 5964054

[goddard-4] جودارد، ستيفن ت. (1983)، "التصنيف في البطولات واتخاذ القرارات الجماعية"، مجلة علوم الإدارة ، 29 (12): 1384-1392 ، doi : 10.1287/mnsc.29.12.1384 ، MR 0809110 لاحظ أن الخوارزمية التي اقترحها جودارد لإيجاد تصنيفات الحد الأدنى من الانتهاكات غير صحيحة

[vdym-5] فازيري، باباك؛ دابادغاو، شوناك؛ ييه، يوهويرن ؛ مورين، توماس ل. (يناير 2018)، "خصائص أساليب تصنيف الرياضة" (ملف PDF) ، مجلة جمعية بحوث العمليات ، 69 (5): 776-787 ، doi : 10.1057/s41274-017-0266-8 ، S2CID 51887586

[cfr-6] كوبرسميث، دون ؛ فليشر، ليزا ك.؛ روردا، أتري (2010)، "الترتيب حسب عدد مرات الفوز المرجحة يعطي تصنيفًا جيدًا للبطولات المرجحة"، معاملات ACM في الخوارزميات ، 6 (3): A55:1–A55:13، doi : 10.1145/1798596.1798608 ، MR 2682624 ، S2CID 18416

[seyfarth-7] سيفارث، روبرت م. (نوفمبر 1976)، "العلاقات الاجتماعية بين إناث البابون البالغات"، سلوك الحيوان ، 24 (4): 917-938 ، doi : 10.1016/s0003-3472(76)80022-x ، S2CID 54284406

[drafthorse-8] إستيب، دي كيو؛ كرويل-ديفيس، إس إل؛ إيرل-كوستيلو، إس-إيه؛ بيتي، إس إيه (يناير 1993)، "تغيرات في السلوك الاجتماعي لأفراس الخيول الثقيلة (Equus caballus) بالتزامن مع الولادة"، مجلة علم سلوك الحيوان التطبيقي ، 35 (3): 199-213 ، doi : 10.1016/0168-1591(93)90137-e

[cockroach-9] إيكوورت، جورج سي. (أبريل 2019)، "الهيمنة في الصرصور (نوفويتا)"، سلوك الحشرات ، مطبعة سي آر سي، ص 120-126 ، doi : 10.1201/9780429049262-18 ، ISBN 978-0-429-04926-2، S2CID 203898549

[slater-10] سلاتر، باتريك (1961)، "التناقضات في جدول المقارنات الزوجية"، Biometrika ، 48 ( 3-4 ): 303-312 ، doi : 10.1093/biomet/48.3-4.303 ، JSTOR 2332752

[brunk-11] برونك، إتش دي (1960)، "النماذج الرياضية للترتيب من المقارنات الزوجية"، مجلة الجمعية الإحصائية الأمريكية ، 55 (291): 503-520 ، doi : 10.2307/2281911 ، JSTOR 2281911 ، MR 0115242 نُشرت في شكل أولي كوثيقة ASTIA رقم AD 206 573، القوات الجوية الأمريكية، مكتب البحوث العلمية، نوفمبر 1958، hdl : 2027/mdp.39015095254010

[rt64-12] تومسون، دبليو إيه جونيور؛ ريماج، راسل جونيور (1964)، "التصنيفات من المقارنات الزوجية"، حوليات الإحصاء الرياضي ، 35 (2): 739-747 ، doi : 10.1214/aoms/1177703572 ، JSTOR 2238526 ، MR 0161419

[kemeny-13] كيميني، جون ج. (خريف 1959)، "الرياضيات بدون أرقام"، ديدالوس ، 88 (4): 577-591 ، JSTOR 20026529

[KarpinskiSchudy-14] 1 2 كاربينسكي، ماريك ؛ شودي، وارن (2010)، "خوارزميات أسرع لبطولة مجموعة قوس التغذية الراجعة، وتجميع رتبة كيميني، وبطولة الوساطة"، في تشيونغ، أوتفريد ؛ تشوا، كيونغ يونغ؛ بارك، كونسو (محررون)، الخوارزميات والحوسبة - الندوة الدولية الحادية والعشرون، ISAAC 2010، جزيرة جيجو، كوريا، 15-17 ديسمبر 2010، وقائع، الجزء الأول ، سلسلة محاضرات في علوم الحاسوب، المجلد 6506، سبرينغر، الصفحات 3-14 ، arXiv : 1006.4396 ، doi : 10.1007/978-3-642-17517-6_3 ، ISBN 978-3-642-17516-9، S2CID 16512997

[unger-15] 1 2 أونغر، ستيفن هـ. (26 أبريل 1957)، دراسة لشبكات التغذية الراجعة المنطقية غير المتزامنة ، التقارير الفنية، المجلد 320، معهد ماساتشوستس للتكنولوجيا، مختبر أبحاث الإلكترونيات، hdl : 1721.1/4763

[clock-16] فيهر، جون ر.؛ جوردان، هاري ف. (ديسمبر 1995)، "وضع بوابات الساعة في دوائر الإلكترونيات الضوئية بتقنية زمن الرحلة"، البصريات التطبيقية ، 34 (35): 8125-8136 ، Bibcode : 1995ApOpt..34.8125F ، doi : 10.1364/ao.34.008125 ، PMID 21068927

[rh68-17] روزن، إدوارد م.؛ هينلي، إرنست ج. (صيف 1968)، "القياس الكمي الجديد" ، تعليم الهندسة الكيميائية ، 2 (3): 120-125 ، مؤرشف من الأصل في 2021-08-02 ، تم استرجاعه في 2021-08-02

[dett98-18] دي باتيستا، جوزيبي؛ إيدز، بيتر ؛ تاماسيا، روبرتو ؛ توليس، يوانيس ج. (1998)، "الرسومات الطبقية للرسوم البيانية الموجهة"، رسم الرسوم البيانية: خوارزميات لتصور الرسوم البيانية ، برنتيس هول ، ص 265-302 ، ISBN 978-0-13-301615-4

[bm01-19] باسترت، أوليفر؛ ماتوسزوسكي، كريستيان (2001)، "الرسومات الطبقية للرسوم البيانية الموجهة"، في كوفمان، مايكل؛ فاغنر، دوروثيا (محرران)، رسم الرسوم البيانية: الأساليب والنماذج ، سلسلة محاضرات في علوم الحاسوب، المجلد 2025، سبرينغر-فيرلاغ، الصفحات 87-120 ، doi : 10.1007/3-540-44969-8_5 ، ISBN 978-3-540-42062-0

[df01-20] ديميتريسكو، كاميل؛ فينوتشي، إيرين (2001)، "كسر الحلقات "الصحيحة" والحصول على الرسم "الأفضل"، مجلة ACM للخوارزميات التجريبية ، 6 : 171-182 ، MR 2027115

[enss-21] 1 2 3 إيفن، جي.؛ ناور، ج .؛ شيبر، ب .؛ سودان، م. (1998)، "تقريب مجموعات التغذية الراجعة الدنيا والقطع المتعددة في الرسوم البيانية الموجهة"، Algorithmica ، 20 (2): 151-174 ، doi : 10.1007/PL00009191 ، MR 1484534 ، S2CID 2437790

[minoura-22] 1 2 مينورا، توشيمي (1982)، "إعادة النظر في تجنب حالات الجمود"، مجلة ACM ، 29 (4): 1023-1048 ، doi : 10.1145/322344.322351 ، MR 0674256 ، S2CID 5284738

[missik-23] ميشرا، سوناكا؛ سيكدار، كريباسيندو (2004)، "حول إمكانية تقريب الترتيب الخطي ومسائل التحسين NP ذات الصلة على الرسوم البيانية"، الرياضيات التطبيقية المنفصلة ، 136 ( 2-3 ): 249-269 ، doi : 10.1016/S0166-218X(03)00444-X ، MR 2045215

[Hecht-24] 1 2 هيشت، مايكل (2017)، "تحديدات دقيقة لمجموعات التغذية الراجعة"، نظرية أنظمة الحوسبة ، 62 (5): 1048-1084 ، arXiv : 1702.07612 ، doi : 10.1007/s00224-017-9777-6 ، S2CID 18394348

[pa92-25] بارك، س.؛ أكيرز، س.ب. (1992)، "طريقة فعالة لإيجاد مجموعة أقواس التغذية الراجعة الدنيا في الرسوم البيانية الموجهة"، وقائع ندوة IEEE الدولية للدوائر والأنظمة لعام 1992 (ISCAS '92) ، المجلد 4، الصفحات 1863-1866 ، doi : 10.1109/iscas.1992.230449 ، ISBN 0-7803-0593-0، S2CID 122603659

[np00-26] 1 2 نوتوف، زئيف؛ بن، ميخال (2000)، "حول التكامل والاستقرار وتكوين حشوات وأغطية الدراجات ثنائية العجلات"، مجلة التحسين التوافقي ، 4 (2): 235-251 ، doi : 10.1023/A:1009802905533 ، MR 1772828 ، S2CID 207632524

[younger-27] يونغر، د. (1963)، "مجموعات أقواس التغذية الراجعة الدنيا للرسم البياني الموجه"، معاملات IEEE في نظرية الدوائر ، 10 (2): 238-245 ، doi : 10.1109/tct.1963.1082116

[lawler-28] لولر، إي. (1964)، "تعليق على مجموعات أقواس التغذية الراجعة الدنيا"، معاملات IEEE في نظرية الدوائر ، 11 (2): 296-297 ، doi : 10.1109/tct.1964.1082291

[bfkkt-29] 1 2 بودليندر، هانز ل .؛ فومين، فيدور ف.؛ كوستر، آري إم سي إيه؛ كراتش، ديتر؛ ثيليكوس، ديميتريوس م. (2012)، "ملاحظة حول الخوارزميات الدقيقة لمسائل ترتيب الرؤوس على الرسوم البيانية"، نظرية أنظمة الحوسبة ، 50 (3): 420-432 ، doi : 10.1007/s00224-011-9312-0 ، hdl : 1956/4556 ، MR 2885638 ، S2CID 9967521

[cllor-30] تشين، جيانر؛ ليو، يانغ؛ لو، سونغجيان؛ أوسوليفان، باري؛ رازغون، إيغور (2008)، "خوارزمية ذات معلمات ثابتة لمسألة مجموعة رؤوس التغذية الراجعة الموجهة"، مجلة ACM ، 55 (5): 1-19 ، doi : 10.1145/1411509.1411511 ، S2CID 1547510

[bknpsw-31] بونامي، مارث؛ كواليك، لوكاس؛ نيدرلوف، يسبر؛ بيليبكزوك، ميخال؛ سوكالا، أركاديوس؛ فروخنا، مارسين (2018)، "حول مجموعة رؤوس التغذية الراجعة الموجهة التي تم تحديدها بواسطة عرض الشجرة"، في براندشتات، أندرياس؛ كولر، إيكهارد؛ مير، كلاوس (محررون)، مفاهيم نظرية الرسم البياني في علوم الحاسوب - ورشة العمل الدولية الرابعة والأربعون، WG 2018، كوتبوس، ألمانيا، 27-29 يونيو 2018، وقائع ، سلسلة محاضرات في علوم الحاسوب، المجلد. 11159، سبرينغر، الصفحات 65-78 ، arXiv : 1707.01470 ، doi : 10.1007/978-3-030-00256-5_6 ، ISBN 978-3-030-00255-8، S2CID 8008855

[ls89-32] لين، ليشين؛ ساهني، سرتاج (1989)، "مسائل حذف الحواف العادلة"، معاملات IEEE للحواسيب ، 38 (5): 756-761 ، doi : 10.1109/12.24280 ، MR 0994519

[ss02-33] شفيكوفسكي، بينو؛ سبيكنماير، إيوالد (2002)، "حول تعداد جميع الحلول الدنيا لمسائل التغذية الراجعة"، الرياضيات التطبيقية المنفصلة ، 117 ( 1-3 ): 253-265 ، doi : 10.1016/S0166-218X(00)00339-5 ، MR 1881280

[compendium-34] 1 2 3 كريسينزي، بييرلويجي؛ كان، فيجو؛ هالدورسون، ماغنوس؛ كاربينسكي، ماريك ؛ ووجينجر، جيرهارد (2000)، "مجموعة أقواس التغذية الراجعة الدنيا" ، مجموعة من مسائل التحسين NP ، مؤرشفة من الأصل في 29-07-2021 ، تم استرجاعها في 29-07-2021

[els-35] إيدز، بيتر ؛ لين، شومين؛ سميث، دبليو إف (1993)، "طريقة استدلالية سريعة وفعالة لمشكلة مجموعة أقواس التغذية الراجعة" ، رسائل معالجة المعلومات ، 47 (6): 319-323 ، doi : 10.1016/0020-0190(93)90079-O ، MR 1256786 ، مؤرشف من الأصل في 22-10-2020 ، تم استرجاعه في 1-08-2021

[bs97-36] بيرغر، بوني ؛ شور، بيتر دبليو. (1997)، "حدود دقيقة لمسألة الرسم البياني الفرعي غير الدوري الأقصى"، مجلة الخوارزميات ، 25 (1): 1-18 ، doi : 10.1006/jagm.1997.0864 ، MR 1474592

[hr94-37] حسين، رفائيل؛ روبنشتاين، شلومي (1994)، "تقريبات لمسألة الرسم البياني الفرعي غير الدوري الأقصى"، رسائل معالجة المعلومات ، 51 (3): 133-140 ، doi : 10.1016/0020-0190(94)00086-7 ، MR 1290207

[newman-38] 1 2 نيومان، ألانثا (يونيو 2000)، تقريب الرسم البياني الفرعي الأقصى غير الدوري (رسالة ماجستير)، معهد ماساتشوستس للتكنولوجيا، hdl : 1721.1/86548 ، كما ورد في غورو سوامي وآخرون (2011)

[gab95-39] 1 2 جابو، هارولد ن. (1995)، "المراكز، والتمثيلات، والتدفقات شبه المعيارية"، مجلة الخوارزميات ، 18 (3): 586-628 ، doi : 10.1006/jagm.1995.1022 ، MR 1334365

[frank-40] 1 2 فرانك، أندراس (1981)، "كيفية إنشاء رسم بياني موجه متصل بقوة"، كومبيناتوريكا ، 1 (2): 145-153 ، doi : 10.1007/BF02579270 ، MR 0625547 ، S2CID 27825518

[ly78-41] 1 2 لوتشيسي، سي إل؛ يونغر، دي إتش (1978)، "نظرية المينيماكس للرسوم البيانية الموجهة"، مجلة جمعية لندن الرياضية ، السلسلة الثانية، 17 (3): 369-374 ، doi : 10.1112/jlms/s2-17.3.369 ، MR 0500618

[gab93-42] 1 2 جابو، هارولد ن. (1993)، "إطار عمل لخوارزميات قياس التكلفة لمسائل التدفق شبه المعياري"، الندوة السنوية الرابعة والثلاثون حول أسس علوم الحاسوب، بالو ألتو، كاليفورنيا، الولايات المتحدة الأمريكية، 3-5 نوفمبر 1993 ، جمعية مهندسي الكهرباء والإلكترونيات، ص 449-458 ، doi : 10.1109/SFCS.1993.366842 ، ISBN 0-8186-4370-6، MR 1328441 ، S2CID 32162097

[gjr85-43] غروتشل، مارتن ؛ يونغر، مايكل؛ راينيلت، غيرهارد (1985)، "حول متعدد السطوح الفرعي غير الدوري"، البرمجة الرياضية ، 33 (1): 28-42 ، doi : 10.1007/BF01582009 ، MR 0809747 ، S2CID 206798683

[ramachandran-44] راماشاندران، فيجايا (1988)، "إيجاد مجموعة أقواس التغذية الراجعة الدنيا في مخططات التدفق القابلة للاختزال"، مجلة الخوارزميات ، 9 (3): 299-313 ، doi : 10.1016/0196-6774(88)90022-3 ، MR 0955140

[MathieuSchudy-45] كينيون-ماثيو، كلير ؛ شودي، وارن (2007)، "كيفية الترتيب بأقل عدد من الأخطاء: خوارزمية تقريبية متعددة الحدود لمجموعة أقواس التغذية الراجعة الموزونة في البطولات"، في جونسون، ديفيد س .؛ فيج، أورييل (محرران)، وقائع الندوة السنوية التاسعة والثلاثين لجمعية آلات الحوسبة حول نظرية الحوسبة، سان دييغو، كاليفورنيا، الولايات المتحدة الأمريكية، 11-13 يونيو 2007 ، الصفحات 95-103 ، doi : 10.1145/1250790.1250806 ، S2CID 9436948 ، ECCC TR06-144 انظر أيضًا النسخة الموسعة للمؤلف. مؤرشفة بتاريخ 15 يناير 2009 في أرشيف الإنترنت (Wayback Machine).

[afk02-46] أرورا، سانجيف ؛ فريز، آلان ؛ كابلان، حاييم (2002)، "إجراء تقريب جديد لمسألة التخصيص مع تطبيقات على مسائل ترتيب الرسوم البيانية الكثيفة" ، البرمجة الرياضية ، 92 (1): 1-36 ، doi : 10.1007/s101070100271 ، MR 1892295 ، S2CID 3207086 ، مؤرشف من الأصل في 2021-08-03 ، تم استرجاعه في 2021-08-03

[karp-47] كارب، ريتشارد م. (1972)، "قابلية الاختزال بين المسائل التوافقية"، تعقيد الحسابات الحاسوبية ، وقائع ندوة مركز أبحاث توماس ج. واتسون التابع لشركة آي بي إم، يوركتاون هايتس، نيويورك، نيويورك: بلينوم، ص 85-103

[gj79-48] غاري، مايكل ر .؛ جونسون، ديفيد س. (1979)، "A1.1: GT8"، الحواسيب والاستعصاء: دليل لنظرية اكتمال NP ، دبليو إتش فريمان، ص 192، ISBN 0-7167-1045-5

[alon-49] ألون، نوغا (2006)، "بطولات التصنيف"، مجلة SIAM للرياضيات المتقطعة ، 20 (1): 137-142 ، doi : 10.1137/050623905 ، MR 2257251

[cty-50] شاربيت، بيير؛ توماسيه، ستيفان؛ يو، أندرس (2007)، "مشكلة مجموعة أقواس التغذية الراجعة الدنيا هي مسألة صعبة من نوع NP بالنسبة للمسابقات" (ملف PDF) ، التوافقية، الاحتمالات والحوسبة ، 16 (1): 1-4 ، doi : 10.1017/S0963548306007887 ، MR 2282830 ، S2CID 36539840

[adp80-51] أوسييلو، ج .؛ داتري، أ.؛ بروتاسي، م. (1980)، "الاختزالات الحافظة للبنية بين مسائل التحسين المحدب"، مجلة علوم الحاسوب والنظم ، 21 (1): 136-153 ، doi : 10.1016/0022-0000(80)90046-X ، MR 0589808

[kann-52] كان، فيجو (1992)، حول إمكانية تقريب مسائل التحسين الكاملة من فئة NP (ملف PDF) (أطروحة دكتوراه)، قسم التحليل العددي وعلوم الحاسوب، المعهد الملكي للتكنولوجيا، ستوكهولم، مؤرشفة (ملف PDF) من الأصل بتاريخ 29-12-2010 ، تم استرجاعها بتاريخ 11-10-2007

[ds05-53] دينور، إيريت ؛ صفرا، صموئيل (2005)، "حول صعوبة تقريب غطاء الرؤوس الأدنى" (ملف PDF) ، حوليات الرياضيات ، 162 (1): 439-485 ، doi : 10.4007/annals.2005.162.439 ، مؤرشف (ملف PDF) من الأصل في 20 سبتمبر 2009 ، تم استرجاعه في 29 يوليو 2021 نسخة أولية في دينور، إيريت ؛ صفرا، صموئيل (2002)، "أهمية التحيز"، في ريف، جون هـ. (محرر)، وقائع الندوة السنوية الرابعة والثلاثين لجمعية آلات الحوسبة حول نظرية الحوسبة، 19-21 مايو 2002، مونتريال، كيبيك، كندا ، ص 33-42 ، doi : 10.1145/509907.509915 ، ISBN 1-58113-495-9، S2CID 1235048

[ghmrc-54] غورو سوامي، فينكاتيسان ؛ هاستاد، يوهان ؛ مانوكاران، راجسيكار؛ راغافيندرا، براساد؛ شاريكار، موسى (2011)، "التغلب على الترتيب العشوائي صعب: كل مسألة إرضاء قيود ترتيبية مقاومة للتقريب" (ملف PDF) ، مجلة SIAM للحوسبة ، 40 (3): 878-914 ، doi : 10.1137/090756144 ، MR 2823511 ، مؤرشف (ملف PDF) من الأصل في 31-07-2021 ، تم استرجاعه في 31-07-2021

[bp18-55] بونيه، إدوارد؛ باشوس، فانجيليس ث. (2018)، "التخفيف والتقريب شبه الأسي"، أكتا إنفورماتيكا ، 55 (1): 1-15 ، arXiv : 1402.2843 ، doi : 10.1007/s00236-016-0281-2 ، MR 3757549 ، S2CID 3136275

[lovasz-56] لوفاس، لازلو (1976)، "حول نظريتين من نظريات المينيماكس في الرسم البياني"، مجلة نظرية التوافيق ، السلسلة ب، 21 (2): 96-103 ، doi : 10.1016/0095-8956(76)90049-6 ، MR 0427138

[bn90-57] بار-نوي، أموتز؛ ناور، جوزيف (1990)، "الفرز، ومجموعات التغذية الراجعة الدنيا، ومسارات هاميلتون في البطولات"، مجلة SIAM للرياضيات المتقطعة ، 3 (1): 7-20 ، doi : 10.1137/0403002 ، MR 1033709

[spencer-58] سبنسر، ج. (1980)، "الترتيب الأمثل للبطولات غير القابلة للترتيب"، مجلة Periodica Mathematica Hungarica ، 11 (2): 131-144 ، doi : 10.1007/BF02017965 ، MR 0573525 ، S2CID 119894999

[fdlv-59] فرنانديز دي لا فيغا، و. (1983)، "حول الحد الأقصى لعدد عناصر مجموعة متسقة من الأقواس في بطولة عشوائية"، مجلة نظرية التوافيق ، السلسلة ب، 35 (3): 328-332 ، doi : 10.1016/0095-8956(83)90060-6 ، MR 0735201

[bhirt-60] بارتيليمي، جان بيير؛ هودري، أوليفييه؛ إيزاك، غارث؛ روبرتس، فريد س .؛ تيسمان، باري (1995)، "عدد الانعكاس للرسم البياني الموجه"، الرياضيات التطبيقية المنفصلة ، 60 ( 1-3 ): 39-76 ، doi : 10.1016/0166-218X(94)00042-C ، MR 1339075

[in04-61] إيزاك، غارث؛ نارايان، دارين أ. (2004)، "تصنيف البطولات التي تحتوي على بطولة غير دورية كمجموعة أقواس تغذية راجعة دنيا" ، رسائل معالجة المعلومات ، 92 (3): 107-111 ، doi : 10.1016/j.ipl.2004.07.001 ، MR 2095357

[hmssy-62] هوانغ، هاو؛ ما، جي؛ شابيرا، آصف؛ سوداكوف، بيني ؛ يوستر، رافائيل (2013)، "مجموعات أقواس التغذية الراجعة الكبيرة، والرسوم البيانية الفرعية ذات الدرجة الدنيا العالية، والدورات الطويلة في الرسوم البيانية الموجهة الأويلرية"، التوافقية، الاحتمالات والحوسبة ، 22 (6): 859-873 ، arXiv : 1202.2602 ، doi : 10.1017/S0963548313000394 ، hdl : 20.500.11850/73894 ، MR 3111546 ، S2CID 7967738

[hba-63] هاناور، كاثرين. براندنبورغ، فرانز جوزيف؛ أوير، كريستوفر (2013)، “حدود عليا مشددة للحد الأدنى من مجموعات ردود الفعل من الرسوم البيانية العادية”، في أندرياس براندستات؛ يانسن، كلاوس؛ Reischuk, Rüdiger (eds.)، المفاهيم النظرية للرسم البياني في علوم الكمبيوتر - ورشة العمل الدولية التاسعة والثلاثين، WG 2013، لوبيك، ألمانيا، 19-21 يونيو 2013، أوراق منقحة ، ملاحظات محاضرة في علوم الكمبيوتر، المجلد. 8165، سبرينغر، الصفحات من 298 إلى 309، دوى : 10.1007/978-3-642-45043-3_26 ، ISBN 978-3-642-45042-6MR 3139198

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[15]

[16]

[17]

[18]

[19]

[20]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]

[ 32 ]

[ 33 ]

[ 34 ]

35

36

[

[ 38 ]

[ 39 ]

[ 40 ]

[ 41 ]

42 ]

[ 43 ]

[ 44 ]

[ 45 ]

[ 46 ]

[ 47 ]

[ 48 ]

[ 49 ]

[ 50 ]

[ 51 ]

[ 52 ]

[ 53 ]

54

55

[ 56 ]

[ 57 ]

58

59 ]

[ 60 ]

[ 61 ]

62 ] إذا

[ 63 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗