Minimum 2-distance coloring of planar graphs and channel assignment

A 2-distance k-coloring of a graph G is a proper k-coloring such that any two vertices at distance two get different colors. \(\chi _{2}(G)\)=min{k|G has a 2-distance k-coloring}. Wegner conjectured that for each planar graph G with maximum degree \(\Delta \), \(\chi _2(G) \le 7\) if \(\Delta \le 3\), \(\chi _2(G) \le \Delta +5\) if \(4\le \Delta \le 7\) and \(\chi _2(G) \le \lfloor \frac{3\Delta }{2}\rfloor +1\) if \(\Delta \ge 8\). In this paper, we prove that: (1) If G is a planar graph with maximum degree \(\Delta \le 5\), then \(\chi _{2}(G)\le 20\); (2) If G is a planar graph with maximum degree \(\Delta \ge 6\), then \(\chi _{2}(G)\le 5\Delta -7\).     

The matching extension problem in general graphs is co-NP-complete

A simple connected graph G with 2n vertices is said to be k-extendable for an integer k with \(0<k<n\) if G contains a perfect matching and every matching of cardinality k in G is a subset of some perfect matching. Lakhal and Litzler (Inf Process Lett 65(1):11–16, 1998) discovered a polynomial algorithm that decides whether a bipartite graph is k-extendable. For general graphs, however, it has been an open problem whether there exists a polynomial algorithm. The new result presented in this paper is that the extendability problem is co-NP-complete.     

A quadratic time exact algorithm for continuous connected 2-facility location problem in trees

This paper studies the continuous connected 2-facility location problem (CC2FLP) in trees. Let \(T = (V, E, c, d, \ell , \mu )\) be an undirected rooted tree, where each node \(v \in V\) has a weight \(d(v) \ge 0\) denoting the demand amount of v as well as a weight \(\ell (v) \ge 0\) denoting the cost of opening a facility at v, and each edge \(e \in E\) has a weight \(c(e) \ge 0\) denoting the cost on e and is associated with a function \(\mu (e,t) \ge 0\) denoting the cost of opening a facility at a point x(e, t) on e where t is a continuous variable on e. Given a subset \(\mathcal {D} \subseteq V\) of clients, and a subset \(\mathcal {F} \subseteq \mathcal {P}(T)\) of continuum points admitting facilities where \(\mathcal {P}(T)\) is the set of all the points on edges of T, when two facilities are installed at a pair of continuum points \(x_1\) and \(x_2\) in \(\mathcal {F}\), the total cost involved in CC2FLP includes three parts: the cost of opening two facilities at \(x_1\) and \(x_2\), K times the cost of connecting \(x_1\) and \(x_2\), and the cost of all the clients in \(\mathcal {D}\) connecting to some facility. The objective is to open two facilities at a pair of continuum points in \(\mathcal {F}\) to minimize the total cost, for a given input parameter \(K \ge 1\). This paper focuses on the case of \(\mathcal {D} = V\) and \(\mathcal {F} = \mathcal {P}(T)\). We first study the discrete version of CC2FLP, named the discrete connected 2-facility location problem (DC2FLP), where two facilities are restricted to the nodes of T, and devise a quadratic time edge-splitting algorithm for DC2FLP. Furthermore, we prove that CC2FLP is almost equivalent to DC2FLP in trees, and develop a quadratic time exact algorithm based on the edge-splitting algorithm. Finally, we adapt our algorithms to the general case of \(\mathcal {D} \subseteq V\) and \(\mathcal {F} \subseteq \mathcal {P}(T)\).     

Reliability evaluation of a multicast over coded packet networks

Network coding is a generalization of conventional routing methods that allows a network node to code information flows before forwarding them. While it has been theoretically proved that network coding can achieve maximum network throughput, theoretical results usually do not consider the stochastic nature in information processing and transmission, especially when the capacity of each arc becomes stochastic due to failure, attacks, or maintenance. Hence, the reliability measurement of network coding becomes an important issue to evaluate the performance of the network under various system settings. In this paper, we present analytical expressions to measure the reliability of multicast communications in coded networks, where network coding is most promising. We define the probability that a multicast rate can be transmitted through a coded packet network under a total transmission cost constraint as the reliability metric. To do this, we first introduce an exact mathematical formulation to construct multicast connections over coded packet networks under a limited transmission cost. We then propose an algorithm based on minimal paths to calculate the reliability measurement of multicast connections and analyze the complexity of the algorithm. Our results show that the reliability of multicast routing with network coding improved significantly compared to the case of multicast routing without network coding.     

A feasibility approach for constructing combinatorial designs of circulant type

In this work, we propose an optimization approach for constructing various classes of circulant combinatorial designs that can be defined in terms of autocorrelation. The problem is formulated as a so-called feasibility problem having three sets, to which the Douglas–Rachford projection algorithm is applied. The approach is illustrated on three different classes of circulant combinatorial designs: circulant weighing matrices, D-optimal matrices of circulant type, and Hadamard matrices with two circulant cores. Furthermore, we explicitly construct two new circulant weighing matrices, a CW(126, 64) and a CW(198, 100), whose existence was previously marked as unresolved in the most recent version of Strassler’s table.     

A continuous characterization of the maximum vertex-weighted clique in hypergraphs

For a simple graph G on n vertices with adjacency matrix A, Motzkin and Strauss established a remarkable connection between the clique number and the global maximum value of the quadratic programm: \(\textit{max}\{ \mathbf {x}^T A \mathbf {x}\}\) on the standard simplex: \(\{\sum _{i=1}^{n} x_i =1, x_i \ge 0 \}\). In Gibbons et al. (Math Oper Res 122:754–768, 1997), an extension of the Motzkin–Straus formulation was provided for the vertex-weighted clique number of a graph. In this paper, we provide a continuous characterization of the maximum vertex-weighted clique problem for vertex-weighted uniform hypergraphs.     

Blocking Rumor by Cut

In this paper, a rumor blocking problem is studied with an objective function which is neither submodular or supermodular. We will prove that this problem is NP-hard and give a data-dependent approximation with sandwich method. In addition, we show that every set function has a pair of monotone nondecreasing modular functions as upper bound and lower bound, respectively.     

Legitimacy theory may explain the failure of global adoption of IFRS: the case of Europe and the U.S.

We investigate the reasons why “adoption” of one set of globally accepted accounting standards is presently unachievable. By “adoption” we mean that a jurisdiction incorporates IFRS instantly as its national accounting as issued by the IASB. We state that the IASB has used a Legitimacy Theory strategy to gain acceptance of its standards by more than 120 countries across the globe but it has only gained pseudo-“adoption” (not as published by the IASB) of its standards by many countries. We contend that achieving policing and enforcement of its standards globally has proven to be empirically illusive. This legitimacy deficit may explain why convergence between the IASB and FASB is currently idle. We offer a possible solution to bridging the legitimacy gap of global adoption of IFRS. We propose an internationally respected regulator and suggest the IOSCO for this role through its participation in the IFRS Foundation Monitoring Board for policing and enforcement of IFRS for cross-listed firms reporting in compliance with IFRS so that the IASB’s output legitimacy may be achieved globally.     

The role of weighting in corporate governance ratings

This methodological paper highlights the differences and the resulting implications from the application of the three most commonly applied weighting index methods to measuring corporate governance quality at an aggregate level: the Dichotomous; the partial compliance (PC) unweighted; and the Experts’ methods. In particular, first, we demonstrate how each method is applied and provide the details needed for readers to replicate each method. Second, we employ these methods on a sample of companies and compare the corresponding scores by testing their differences statistically. Third, as an indicative example of the potential implications arising from the use of these measures, we test whether the relation between market value and corporate governance levels differs, depending on the method applied. We find that the three methods produce significantly different overall and relative (i.e., ranking order) scores and, consequently, the relation between market value and corporate governance levels differs, depending on the method applied. Thus, we contribute to the corporate governance literature by showing that weighting in corporate governance indices matters and we recommend simultaneous application of at least two methods (i.e., the PC unweighted and the Experts’ methods) for deriving robust findings.     

Does the capital of social capital matter? Relational resources of the board and the performance of Brazilian companies

Based on theories of social capital, in this study, we seek to assess the impact of a board’s social capital on the market value of companies listed on the Brazilian stock exchange. As our indicator of social capital, we use the relational resources identified in the direct, indirect and heterogeneous ties of the board. Employing panel data from 508 observations, our results indicate that heterogeneous relational resources have a stronger and more significant influence than the resources available from board members’ direct relationships. Additionally, as the effects of board interlock are endogenously determined by several factors related to the firm level, we seek to mitigate the endogeneity problem using models of instrumental variables and simultaneous equations. Our hypotheses were consistent after controlling for endogeneity. We also check whether the board’s social capital could present a U-inverted effect on the market value. This relationship was only plausible in social capital by indirect ties. Finally, we isolate the effect of relational resources within and between industries on Tobin’s Q. There was no significant effect through interlocks within the same industry. However, ties with companies in several other industries were significant.