Search

The state-owned power Electricity Generating Authority of Thailand (EGAT), a monopoly market in charge of producing, distributing, and wholesaling power, is the focal point of Thailand's electricity market. Although the government has encouraged people to install on-grid solar panels to sell electricity as producers and retail consumers, the price mechanism, i.e., purchasing price and selling prices, is still unilaterally determined by the government. Therefore, we are interested in studying the case where blockchain can be used as a free trading platform. Without involving buying or selling from the government, this research presents a model of fully traded price mechanisms. Based on the study results of the double auction system, data on buying and selling prices of electrical energy in Thailand were used as the initial data for the electricity peer-to-peer free-trading model. Then, information was obtained to analyze the trading price trends by using the law of demand and supply in addition to the principle of the bipartite graph. The price trend results agree well with those of price equilibrium equations. Therefore, we firmly believe that the model we offer can be traded in a closed system of free-trade platforms. In addition, the players in the system can help to determine the price trend that will occur according to various parameters and will cause true fairness in the sustainable electricity supply chain industry in Thailand. [ABSTRACT FROM AUTHOR]

The median of a graph G with weighted vertices is the set of all vertices x minimizing the sum of weighted distances from x to the vertices of G. For any integer p ≥ 2 , we characterize the graphs in which, with respect to any non-negative weights, median sets always induce connected subgraphs in the pth power G p of G. This extends some characterizations of graphs with connected medians (case p = 1 ) provided by Bandelt and Chepoi (SIAM J Discrete Math 15(2):268–282, 2002. https://doi.org/10.1137/S089548019936360X). The characteristic conditions can be tested in polynomial time for any p. We also show that several important classes of graphs in metric graph theory, including bridged graphs (and thus chordal graphs), graphs with convex balls, bucolic graphs, and bipartite absolute retracts, have G 2 -connected medians. Extending the result of Bandelt and Chepoi that basis graphs of matroids are graphs with connected medians, we characterize the isometric subgraphs of Johnson graphs and of halved-cubes with connected medians. [ABSTRACT FROM AUTHOR]

Suppose that you wish to sample a random graph G over n vertices and m edges conditioned on the event that G does not contain a "small" t-size graph H (e.g., clique) as a subgraph. Assuming that most such graphs are H-free, the problem can be solved by a simple rejected-sampling algorithm (that tests for t-cliques) with an expected running time of nO(t). Is it possible to solve the problem in a running time that does not grow polynomially with nt? In this paper, we introduce the general problem of sampling a "random looking" graph G with a given edge density that avoids some arbitrary predefined t-size subgraph H. As our main result, we show that the problem is solvable with respect to some specially crafted k-wise independent distribution over graphs. That is, we design a sampling algorithm for k-wise independent graphs that supports efficient testing for subgraph-freeness in time f(t). nc, where f is a function of t and the constant c in the exponent is independent of t. Our solution extends to the case where both G and H are d-uniform hypergraphs. We use these algorithms to obtain the first probabilistic construction of constant-degree polynomially unbalanced expander graphs whose failure probability is negligible in n (i.e., n (1)). In particular, given constants d > c 1, we output a bipartite graph that has n left nodes and nc right nodes with right-degree of d so that any right set of size at most n (1) expands by factor of (d). This result is extended to the setting of unique expansion as well. We observe that such a negligible-error construction can be employed in many useful settings and present applications in coding theory (batch codes and lowdensity parity-check codes), pseudorandomness (low-bias generators and randomness extractors), and cryptography. Notably, we show that our constructions yield a collection of polynomial-stretch locally computable cryptographic pseudorandom generators based on Goldreich's one-wayness assumption resolving a central open problem in the area of parallel-time cryptography (e.g., Applebaum, Ishai, and Kushilevitz [SIAM J. Comput., 36 (2006), pp. 845-888] and Ishai et al. [Proceedings of the 40th Annual ACM Symposium on Theory of Computing, ACM, 2008, pp. 433-442]). [ABSTRACT FROM AUTHOR]

We correct an error in the appendix of [N. Alon et al., SIAM J. Discrete Math., 34 (2020), pp. 885-903] and prove that it is NP-hard to approximate the size of a maximum induced matching of a bipartite graph within any constant factor. [ABSTRACT FROM AUTHOR]

We study kernelization of classic hard graph problems when the input graphs fulfill triadic closure properties. More precisely, we consider the recently introduced parameters closure number c and weak closure number γ (Fox et al. SIAM J Comput 49(2):448–464, 2020) in addition to the standard parameter solution size k. The weak closure number γ of a graph is upper-bounded by the minimum of its closure number c and its degeneracy d. For Capacitated Vertex Cover, Connected Vertex Cover, and Induced Matching we obtain the first kernels of size k O (γ) , k O (γ) , and (γ k) O (γ) , respectively. This extends previous results on the kernelization of these problems on degenerate graphs. These kernels are essentially tight as these problems are unlikely to admit kernels of size k o (γ) by previous results on their kernelization complexity on degenerate graphs (Cygan et al. ACM Trans Algorithms 13(3):43:1–43:22, 2017). For Capacitated Vertex Cover, we show that even a kernel of size k o (c) is unlikely. In contrast, for Connected Vertex Cover, we obtain a kernel with O (c k 2) vertices. Moreover, we prove that searching for an induced subgraph of order at least k belonging to a hereditary graph class G admits a kernel of size k O (γ) when G contains all complete and all edgeless graphs. Finally, we provide lower bounds for the kernelization of Independent Set on graphs with constant closure number c and kernels for Dominating Set on weakly closed split graphs and weakly closed bipartite graphs. [ABSTRACT FROM AUTHOR]

Maximally recoverable codes are codes designed for distributed storage which combine quick recovery from single node failure and optimal recovery from catastrophic failure. Gopalan et al. [Maximally recoverable codes for grid-like topologies, in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2017, pp. 2092--2108] studied the alphabet size needed for such codes in grid topologies and gave a combinatorial characterization for it. Consider a labeling of the edges of the complete bipartite graph Kn,n, with labels coming from F2d, that satisfies the following condition: for any simple cycle, the sum of the labels over its edges is nonzero. The minimal d where this is possible controls the alphabet size needed for maximally recoverable codes in n×n grid topologies. Prior to the current work, it was known that d is between (log n)² and n log n. We improve both bounds and show that d is linear in n. The upper bound is a recursive construction which beats the random construction. The lower bound follows by first relating the problem to the independence number of the Birkhoff polytope graph, and then providing tight bounds for it using the representation theory of the symmetric group. [ABSTRACT FROM AUTHOR]

A bipartite graph is subcubic if it is an irregular bipartite graph with maximum degree three. In this paper, we prove that the asymptotic value of maximum spectral radius over subcubic bipartite graphs of order n is 3 − Θ ( π 2 n 2 ). Our key approach is taking full advantage of the eigenvalues of a certain tridiagonal matrix, due to Willms [SIAM J. Matrix Anal. Appl. 30 (2008) 639–656]. Moreover, for large maximum degree, i.e., the maximum degree is at least ⌊ n / 2 ⌋ , we characterize irregular bipartite graphs with maximum spectral radius. For general maximum degree, we present an upper bound on the spectral radius of irregular bipartite graphs in terms of the order and maximum degree. [ABSTRACT FROM AUTHOR]