查看更多>>摘要：? 2021 Elsevier B.V.We give two approximation algorithms solving the Stochastic Boolean Function Evaluation (SBFE) problem for symmetric Boolean functions. The first is an O(logn)-approximation algorithm, based on the submodular goal-value approach of Deshpande, Hellerstein and Kletenik. Our second algorithm, which is simple, is based on the algorithm solving the SBFE problem for k-of-n functions, due to Salloum, Breuer, and Ben-Dov. It achieves a (B?1) approximation factor, where B is the number of blocks of 0’s and 1’s in the standard vector representation of the symmetric Boolean function. As part of the design of the first algorithm, we prove that the goal value of any symmetric Boolean function is less than n(n+1)/2. Finally, we give an example showing that for symmetric Boolean functions, minimum expected verification cost and minimum expected evaluation cost are not necessarily equal. This contrasts with a previous result, given by Das, Jafarpour, Orlitsky, Pan and Suresh, which showed that equality holds in the unit-cost case.
查看更多>>摘要：? 2021 Elsevier B.V.In this article, we answer three questions from the paper (Das, 2021). We observe a tight lower bound for the triameter of trees in terms of order and number of leaves. We show that in a connected block graph any triametral triple of vertices contains a diametral pair and that any diametral pair of vertices can be extended to a triametral triple. We also present several open problems concerning the interplay between triametral triples, diametral pairs and peripheral vertices in median and distance-hereditary graphs.
查看更多>>摘要：? 2021 Elsevier B.V.A vertex in a graph is simplicial if its neighborhood forms a clique. We consider three generalizations of the concept of simplicial vertices: avoidable vertices (also known as OCF-vertices), simplicial paths, and their common generalization avoidable paths. In an earlier version of this paper, published as an extended abstract in the proceedings of the 16th International Symposium on Algorithms and Data Structures (WADS 2019), we presented a general conjecture on the existence of avoidable paths. The conjecture was recently proved by Bonamy et al. (2020). The conjecture—now a theorem—implies a result due to Ohtsuki, Cheung, and Fujisawa from 1976 on the existence of avoidable vertices and a result due to Chvátal, Sritharan, and Rusu from 2002 on the existence of simplicial paths in graphs excluding all sufficiently long induced cycles. In turn, both of these results generalize Dirac's classical result on the existence of simplicial vertices in chordal graphs. We prove that every graph with at least two edges has two avoidable edges, which strengthens the statement of the theorem of Bonamy et al. for the case of paths of length one. We point out a close relationship between avoidable vertices in a graph and its minimal triangulations, and identify new algorithmic uses of avoidable vertices, leading to new polynomially solvable cases of the maximum weight clique problem in two classes of graphs simultaneously generalizing chordal graphs and circular-arc graphs. Finally, we observe that the results about the existence of avoidable vertices and edges have interesting consequences for highly symmetric graphs: in a vertex-transitive graph every induced two-edge path closes to an induced cycle, while in an edge-transitive graph every three-edge path closes to a cycle and every induced three-edge path closes to an induced cycle.
查看更多>>摘要：? 2021 Elsevier B.V.For a given list assignment L of a graph G, an (L,r)-coloring of G is a proper coloring c such that for any vertex v with degree d(v), v is adjacent to vertices of at least min{d(v),r} different color with c(v)∈L(v). The r-hued list chromatic number of G, denoted as χL,r(G), is the least integer k, such that for any v∈V(G) and every list assignment L with |L(v)|=k, G has an (L,r)-coloring. Let K(r)=r+3 if 2≤r≤3, K(r)=?3r/2?+1 if r≥4. In Song et al. (2014), it is proved that if G is a K4-minor-free graph, then χL,r(G)≤K(r)+1. Let K4(n) be the set of all subdivisions of K4 on n vertices. Utilizing the decompositions by Chen et al for K4(7)-minor free graphs in Chen et al. (2020), we prove that if G is a K4(7)-minor free graph, then χL,r(G)≤K(r)+1.
查看更多>>摘要：? 2021Diagnosis plays an important role in measuring the reliability of an interconnection network, and the diagnosability of interconnection networks has been widely investigated. For a system G, Zhang et al. introduced h-extra conditional diagnosability, denoted by th?(G), which is a novel measure of diagnosability. In this paper, several new structural properties of balanced hypercubes have been derived. Based on these properties, the 3-extra conditional diagnosability of an n-dimensional balanced hypercube is determined to be t?3(BHn)=4n?1 for n≥5 under the MM? model.
NSTL
Elsevier