A characterization of linearizable instances of the quadratic minimum spanning tree problem

We investigate special cases of the quadratic minimum spanning tree problem (QMSTP) on a graph \(G=(V,E)\) that can be solved as a linear minimum spanning tree problem. We give a characterization of such problems when G is a complete graph, which is the standard case in the QMSTP literature. We extend our characterization to a larger class of graphs that include complete bipartite graphs and cactuses, among others. Our characterization can be verified in \(O(|E|^2)\) time. In the case of complete graphs and when the cost matrix is given in factored form, we show that our characterization can be verified in O(|E|) time. Related open problems are also indicated.     

On computing a minimum secure dominating set in block graphs

In a graph \(G=(V,E)\), a set \(D \subseteq V\) is said to be a dominating set of G if for every vertex \(u\in V{\setminus }D\), there exists a vertex \(v\in D\) such that \(uv\in E\). A secure dominating set of the graph G is a dominating set D of G such that for every \(u\in V{\setminus }D\), there exists a vertex \(v\in D\) such that \(uv\in E\) and \((D{\setminus }\{v\})\cup \{u\}\) is a dominating set of G. Given a graph G and a positive integer k, the secure domination problem is to decide whether G has a secure dominating set of cardinality at most k. The secure domination problem has been shown to be NP-complete for chordal graphs via split graphs and for bipartite graphs. In Liu et al. (in: Proceedings of 27th workshop on combinatorial mathematics and computation theory, 2010), it is asked to find a polynomial time algorithm for computing a minimum secure dominating set in a block graph. In this paper, we answer this by presenting a linear time algorithm to compute a minimum secure dominating set in block graphs. We then strengthen the known NP-completeness of the secure domination problem by showing that the secure domination problem is NP-complete for undirected path graphs and chordal bipartite graphs.     

Improved mixed-integer programming models for the multiprocessor scheduling problem with communication delays

We revise existing and introduce new mixed-integer programming models for the Multiprocessor scheduling problem with communication delays. The basis for both is the identification of two major modeling strategies one of which can be considered ordering-based, and the other assignment-based. We first reveal redundancies in the encoding of feasible solutions found in present formulations and discuss how they can be avoided. For the assignment-based approach, we propose new inequalities that lead to provably stronger continuous relaxations and better performance in practice. Moreover, we derive a third, novel modeling strategy and show how to more compactly linearize assignment formulations with quadratic constraints. In a comprehensive experimental comparison of representative models that reflect the state-of-the-art in terms of strength and size, we evaluate not only running times but also the obtained lower and upper bounds on the makespan for the harder instances of a large scale benchmark set.     

New bounds for locally irregular chromatic index of bipartite and subcubic graphs

A graph is locally irregular if the neighbors of every vertex v have degrees distinct from the degree of v. A locally irregular edge-coloring of a graph G is an (improper) edge-coloring such that the graph induced on the edges of any color class is locally irregular. It is conjectured that three colors suffice for a locally irregular edge-coloring. In the paper, we develop a method using which we prove four colors are enough for a locally irregular edge-coloring of any subcubic graph admiting such a coloring. We believe that our method can be further extended to prove the tight bound of three colors for such graphs. Furthermore, using a combination of existing results, we present an improvement of the bounds for bipartite graphs and general graphs, setting the best upper bounds to 7 and 220, respectively.     

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.     

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.     

Subset sum problems with digraph constraints

We introduce and study optimization problems which are related to the well-known Subset Sum problem. In each new problem, a node-weighted digraph is given and one has to select a subset of vertices whose total weight does not exceed a given budget. Some additional constraints called digraph constraints and maximality need to be satisfied. The digraph constraint imposes that a node must belong to the solution if at least one of its predecessors is in the solution. An alternative of this constraint says that a node must belong to the solution if all its predecessors are in the solution. The maximality constraint ensures that no superset of a feasible solution is also feasible. The combination of these constraints provides four problems. We study their complexity and present some approximation results according to the type of input digraph, such as directed acyclic graphs and oriented trees.