اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدGraph games and the pizza problem
53
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We propose a class of two person perfect information games based on weighted graphs. One of these games can be described in terms of a round pizza which is cut radially into pieces of varying size. The two players alternately take pieces subject to the following rule: Once the first piece has been chosen, all subsequent selections must be adjacent to the hole left by the previously taken pieces. Each player tries to get as much pizza as possible. The original pizza problem was to settle the conjecture that Player One can always get at least half of the pizza. The conjecture turned out to be false. Our main result is a complete solution of a somewhat simpler class of games, concatenations of stacks and two-ended stacks, and we provide a linear time algorithm for this. The algorithm and its output can be described without reference to games. It produces a certain kind of partition of a given finite sequence of real numbers. The conditions on the partition involve alternating sums of various segments of the given sequence. We do not know whether these partitions have applications outside of game theory. The algorithm leads to a quadratic time algorithm which gives the value and an optimal initial move for pizza games. We also provide some general theory concerning the semigroup of equivalence classes of graph games.
قيم البحث
اقرأ أيضاً
The inverse eigenvalue problem of a given graph $G$ is to determine all possible spectra of real symmetric matrices whose off-diagonal entries are governed by the adjacencies in $G$. Barrett et al. introduced the Strong Spectral Property (SSP) and th
e Strong Multiplicity Property (SMP) in [8]. In that paper it was shown that if a graph has a matrix with the SSP (or the SMP) then a supergraph has a matrix with the same spectrum (or ordered multiplicity list) augmented with simple eigenvalues if necessary, that is, subgraph monotonicity. In this paper we extend this to a form of minor monotonicity, with restrictions on where the new eigenvalues appear. These ideas are applied to solve the inverse eigenvalue problem for all graphs of order five, and to characterize forbidden minors of graphs having at most one multiple eigenvalue.
Satisfiability of boolean formulae (SAT) has been a topic of research in logic and computer science for a long time. In this paper we are interested in understanding the structure of satisfiable and unsatisfiable sentences. In previous work we initia
ted a new approach to SAT by formulating a mapping from propositional logic sentences to graphs, allowing us to find structural obstructions to 2SAT (clauses with exactly 2 literals) in terms of graphs. Here we generalize these ideas to multi-hypergraphs in which the edges can have more than 2 vertices and can have multiplicity. This is needed for understanding the structure of SAT for sentences made of clauses with 3 or more literals (3SAT), which is a building block of NP-completeness theory. We introduce a decision problem that we call GraphSAT, as a first step towards a structural view of SAT. Each propositional logic sentence can be mapped to a multi-hypergraph by associating each variable with a vertex (ignoring the negations) and each clause with a hyperedge. Such a graph then becomes a representative of a collection of possible sentences and we can then formulate the notion of satisfiability of such a graph. With this coarse representation of classes of sentences one can then investigate structural obstructions to SAT. To make the problem tractable, we prove a local graph rewriting theorem which allows us to simplify the neighborhood of a vertex without knowing the rest of the graph. We use this to deduce several reduction rules, allowing us to modify a graph without changing its satisfiability status which can then be used in a program to simplify graphs. We study a subclass of 3SAT by examining sentences living on triangulations of surfaces and show that for any compact surface there exists a triangulation that can support unsatisfiable sentences, giving specific examples of such triangulations for various surfaces.
In 2009, Jonoska, Seeman and Wu showed that every graph admits a route for a DNA reporter strand, that is, a closed walk covering every edge either once or twice, in opposite directions if twice, and passing through each vertex in a particular way. T
his corresponds to showing that every graph has an emph{edge-outer embedding}, that is, an orientable embedding with some face that is incident with every edge. In the motivating application, the objective is such a closed walk of minimum length. Here we give a short algorithmic proof of the original existence result, and also prove that finding a shortest length solution is NP-hard, even for $3$-connected cubic ($3$-regular) planar graphs. Independent of the motivating application, this problem opens a new direction in the study of graph embeddings, and we suggest new problems emerging from it.
The bloom of complex network study, in particular, with respect to scale-free ones, is considerably triggering the research of scale-free graph itself. Therefore, a great number of interesting results have been reported in the past, including bounds
of diameter. In this paper, we focus mainly on a problem of how to analytically estimate the lower bound of diameter of scale-free graph, i.e., how small scale-free graph can be. Unlike some pre-existing methods for determining the lower bound of diameter, we make use of a constructive manner in which one candidate model $mathcal{G^*} (mathcal{V^*}, mathcal{E^*})$ with ultra-small diameter can be generated. In addition, with a rigorous proof, we certainly demonstrate that the diameter of graph $mathcal{G^{*}}(mathcal{V^{*}},mathcal{E^{*}})$ must be the smallest in comparison with that of any scale-free graph. This should be regarded as the tight lower bound.
Assume you have a 2-dimensional pizza with $2n$ ingredients that you want to share with your friend. For this you are allowed to cut the pizza using several straight cuts, and then give every second piece to your friend. You want to do this fairly, t
hat is, your friend and you should each get exactly half of each ingredient. How many cuts do you need? It was recently shown using topological methods that $n$ cuts always suffice. In this work, we study the computational complexity of finding such $n$ cuts. Our main result is that this problem is PPA-complete when the ingredients are represented as point sets. For this, we give a new proof that for point sets $n$ cuts suffice, which does not use any topological methods. We further prove several hardness results as well as a higher-dimensional variant for the case where the ingredients are well-separated.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
