Search

Huber et al. (SIAM J Comput 43:1064–1084, 2014) introduced a concept of skew bisubmodularity, as a generalization of bisubmodularity, in their complexity dichotomy theorem for valued constraint satisfaction problems over the three-value domain, and Huber and Krokhin (SIAM J Discrete Math 28:1828–1837, 2014) showed the oracle tractability of minimization of skew-bisubmodular functions. Fujishige et al. (Discrete Optim 12:1–9, 2014) also showed a min–max theorem that characterizes the skew-bisubmodular function minimization, but devising a combinatorial polynomial algorithm for skew-bisubmodular function minimization was left open. In the present paper we give first combinatorial (weakly and strongly) polynomial algorithms for skew-bisubmodular function minimization.

A symmetric matrix is Robinsonian if its rows and columns can be simultaneously reordered in such a way that entries are monotone nondecreasing in rows and columns when moving toward the diagonal. The adjacency matrix of a graph is Robinsonian precisely when the graph is a unit interval graph, so that Robinsonian matrices form a matrix analogue of the class of unit interval graphs. Here we provide a structural characterization for Robinsonian matrices in terms of forbidden substructures, extending the notion of asteroidal triples to weighted graphs. This implies the known characterization of unit interval graphs and leads to an efficient algorithm for certifying that a matrix is not Robinsonian.

We introduce a new class of structured symmetric matrices by extending the notion of perfect elimination ordering from graphs to weighted graphs or matrices. This offers a common framework capturing common vertex elimination orderings of monotone families of chordal graphs, Robinsonian matrices and ultrametrics. We give a structural characterization for matrices that admit perfect elimination orderings in terms of forbidden substructures generalizing chordless cycles in graphs.

AIMS: Catheter ablation can be lifesaving in ventricular tachycardia (VT) storm, but the underlying substrate in patients with storm is not well characterized. We sought to compare the clinical factors, substrate, and outcomes differences in patients with sustained monomorphic VT who present for catheter ablation with VT storm versus those with a nonstorm presentation. METHODS: Consecutive ischemic (ICM; n = 554) or nonischemic cardiomyopathy patients (NICM; n = 369) with a storm versus nonstorm presentation were studied (ICM storm 186; NICM storm 101). RESULTS: In ICM, storm compared with nonstorm patients had significantly lower left ventricular (LV) ejection fraction (EF), greater number of antiarrhythmic drug (AAD) failures, slower VTs, greater number of scarred LV segments, higher incidence of anterior, septal, and apical endocardial LV scar (all P < 0.05). However, outcomes in follow-up were similar (12-month ventricular arrhythmia [VA]-free survival: 51% vs. 52%, P = 0.6; survival free of death/transplant 75% vs. 87%, P = 0.7). In addition to the above differences, NICM storm patients were also older; however, the extent and distribution of scar was similar except for a higher incidence of lateral endocardial scar in storm patients (P = 0.05). VA-free survival (36% vs. 47%, P = 0.004) and survival free of death/transplant, however, were worse in NICM storm than nonstorm patients (72% vs. 88%, P = 0.001). NICM storm patients had worse VA-free survival than ICM storm patients. CONCLUSION: There are differences in clinical factors and scar patterns in patients undergoing VT ablation who present with VT storm versus those with a nonstorm presentation. Clinical outcomes are worse in NICM storm patients.

We consider the problems of completing a low-rank positive semidefinite square matrix M or a low-rank rectangular matrix N from a given subset of their entries. We study the local and global uniqueness of such completions by analyzing the structure of the graphs determined by the positions of the known entries of M or N. We show that, in the generic setting, the unique completability testing of rectangular matrices is a special case of the unique completability testing of positive semidefinite matrices. We prove that a generic partially filled semidefinite n×n matrix is globally uniquely rank d completable if any principal minor of size n−1 is locally uniquely rank d completable. These results are based on new geometric observations that extend similar results of the theory of rigid frameworks. We also give an example showing that global completability is not a generic property in R2. We provide sufficient conditions for local and global unique completability of a partially filled matrix in terms of either the minimum number of known entries per row or the total number of known entries.

We consider planar bar-and-joint frameworks with discrete point group symmetry in which the joint positions are as generic as possible subject to the symmetry constraint. We provide combinatorial characterizations for symmetry-forced rigidity of such structures with rotation symmetry or dihedral symmetry of order 2k with odd k, unifying and extending previous work on this subject. We also explore the matroidal background of our results and show that the matroids induced by the row independence of the orbit matrices of the symmetric frameworks are isomorphic to gain sparsity matroids defined on the quotient graph of the framework, whose edges are labeled by elements of the corresponding symmetry group. The proofs are based on new Henneberg type inductive constructions of the gain graphs that correspond to the bases of the matroids in question, which can also be seen as symmetry preserving graph operations in the original graph.

Recently, Eisenbrand, Pach, Rothvoss, and Sopher studied the function M(m, n), which is the largest cardinality of a convexly independent subset of the Minkowski sum of some planar point sets P and Q with |P| = m and |Q| = n. They proved that M(m,n)=O(m^{2/3}n^{2/3}+m+n), and asked whether a superlinear lower bound exists for M(n,n). In this note, we show that their upper bound is the best possible apart from constant factors.

info:eu-repo/semantics/published

An optimization approach is presented for enumerating pin-jointed bistable compliant mechanisms. In the first stage, the statically determinate trusses with non-crossing members containing a given set of nodes and some pre-defined members are regarded as minimally rigid framework or a Laman framework, and are enumerated without repetitions by the graph enumeration algorithm. In the second stage, the nodal locations and the cross-sectional areas are optimized under mechanical constraints, where the snapthrough behavior is extensively utilized to produce a pin-jointed bistable compliant mechanism. In the numerical examples, many bistable compliant mechanisms are generated to show the effectiveness of the proposed method.