Maximum weight independent sets in hole- and dart-free graphs

The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. The complexity of the MWIS problem for hole-free graphs is unknown. In this paper, we first prove that the MWIS problem for (hole, dart, gem)-free graphs can be solved in O(n(3))-time. By using this result, we prove that the MWIS problem for (hole, dart)-free graphs can be solved in O(n(4))-time. Though the MWIS problem for (hole, dart, gem)-free graphs is used as a subroutine, we also give the best known time bound for the solvability of the MWIS problem in (hole, dart, gem)-free graphs. (C) 2012 Elsevier B.V. All rights reserved.

Genome-wide scans of three independent sets of 90 Irish multiplex schizophrenia families and follow-up of selected regions in all families provides evidence for multiple susceptibility genes

From our linkage study of Irish families with a high density of schizophrenia, we have previously reported evidence for susceptibility genes in regions 5q21-31, 6p24-21, 8p22-21, and 10p15-p11. In this report, we describe the cumulative results from independent genome scans of three a priori random subsets of 90 families each, and from multipoint analysis of all 270 families in ten regions. Of these ten regions, three (13q32, 18p11-q11, and 18q22-23) did not generate scores above the empirical baseline pairwise scan results, and one (6q13-26) generated a weak signal. Six other regions produced more positive pairwise and multipoint results. They showed the following maximum multipoint H-LOD (heterogeneity LOD) and NPL scores: 2p14-13: 0.89 (P = 0.06) and 2.08 (P = 0.02), 4q24-32: 1.84 (P = 0.007) and 1.67 (P = 0.03), 5q21-31: 2.88 (P= 0.0007), and 2.65 (P = 0.002), 6p25-24: 2.13 (P = 0.005) and 3.59 (P = 0.0005), 6p23: 2.42 (P = 0.001) and 3.07 (P = 0.001), 8p22-21: 1.57 (P = 0.01) and 2.56 (P = 0.005), 10p15-11: 2.04 (P = 0.005) and 1.78 (P = 0.03). The degree of 'internal replication' across subsets differed, with 5q, 6p, and 8p being most consistent and 2p and 10p being least consistent. On 6p, the data suggested the presence of two susceptibility genes, in 6p25-24 and 6p23-22. Very few families were positive on more than one region, and little correlation between regions was evident, suggesting substantial locus heterogeneity. The levels of statistical significance were modest, as expected from loci contributing to complex traits. However, our internal replications, when considered along with the positive results obtained in multiple other samples, suggests that most of these six regions are likely to contain genes that influence liability to schizophrenia.

Algorithms for Maximum Independent Set in Convex Bipartite Graphs

A bipartite graph G = (V, W, E) is convex if there exists an ordering of the vertices of W such that, for each v. V, the neighbors of v are consecutive in W. We describe both a sequential and a BSP/CGM algorithm to find a maximum independent set in a convex bipartite graph. The sequential algorithm improves over the running time of the previously known algorithm and the BSP/CGM algorithm is a parallel version of the sequential one. The complexity of the algorithms does not depend on |W|.

The construction contract bidder homogeneity assumption : an empirical test

This paper describes an empirical study to test the proposition that all construction contract bidders are homogeneous ie. they can be treated as behaving collectively in an identical (statistical) manner. Examination of previous analyses of bidding data reveals a flaw in the method of standardising bids across different size contracts and a new procedure is proposed which involves the estimation of a contract datum. Three independent sets of bidding data were then subjected to this procedure and estimates of the necessary distributional parameters obtained. These were then tested against the bidder homogeneity assumption resulting in the conclusion that the assumption may be appropriate for a three parameter log-normal shape, but not for scale and location.

Non-destructive structural integrity assessment of a decommissioned rail wagon system

This paper presents a multi-criteria based approach for nondestructive diagnostic structural integrity assessment of a decommissioned flatbed rail wagon (FBRW) used for road bridge superstructure rehabilitation and replacement applications. First, full-scale vibration and static test data sets are employed in a FE model of the FBRW to obtain the best ‘initial’ estimate of the model parameters. Second, the ‘final’ model parameters are predicted using sensitivity-based perturbation analysis without significant difficulties encountered. Consequently, the updated FBRW model is validated using the independent sets of full-scale laboratory static test data. Finally, the updated and validated FE model of the FBRW is used for structural integrity assessment of a single lane FBRW bridge subjected to the Australian bridge design traffic load.

Distributed Scheduling for Multi-Hop Wireless Networks

We study the performance of greedy scheduling in multihop wireless networks where the objective is aggregate utility maximization. Following standard approaches, we consider the dual of the original optimization problem. Optimal scheduling requires selecting independent sets of maximum aggregate price, but this problem is known to be NP-hard. We propose and evaluate a simple greedy heuristic. We suggest how the greedy heuristic can be implemented in a distributed manner. We evaluate an analytical bound in detail, for the special case of a line graph and also provide a loose bound on the greedy heuristic for the case of an arbitrary graph.

Greedy Scheduling in Multihop Wireless Networks

We study the performance of greedy scheduling in multihop wireless networks where the objective is aggregate utility maximization. Following standard approaches, we consider the dual of the original optimization problem. Optimal scheduling requires selecting independent sets of maximum aggregate price, but this problem is known to be NP-hard. We propose and evaluate a simple greedy heuristic. Analytical bounds on performance are provided and simulations indicate that the greedy heuristic performs well in practice.

Contribution of different physical forces to the disjoining pressure of a thin water film being pressed by an oil droplet

With an objective to understand the nature of forces which contribute to the disjoining pressure of a thin water film on a steel substrate being pressed by an oil droplet, two independent sets of experiments were done. (i) A spherical silica probe approaches the three substrates; mica, PTFE and steel, in a 10 mM electrolyte solution at two different pHs (3 and 10). (ii) The silica probe with and without a smeared oil film approaches the same three substrates in water (pH = 6). The surface potential of the oil film/water was measured using a dynamic light scattering experiment. Assuming the capacity of a substrate for ion exchange the total interaction force for each experiment was estimated to include the Derjaguin-Landau-Verwey-Overbeek (DLVO) force, hydration repulsion, hydrophobic attraction and oil-capillary attraction. The best fit of these estimates to the force-displacement characteristics obtained from the two sets of experiment gives the appropriate surface potentials of the substrates. The procedure allows an assessment of the relevance of a specific physical interaction to an experimental configuration. Two of the principal observations of this work are: (i) The presence of a surface at constant charge, as in the presence of an oil film on the probe, significantly enhances the counterion density over what is achieved when both the surfaces allow ion exchange. This raises the corresponding repulsion barrier greatly. (ii) When the substrate surface is wettable by oil, oil-capillary attraction contributes substantially to the total interaction. If it is not wettable the oil film is deformed and squeezed out. (C) 2010 Elsevier Inc. All rights reserved.

A unified approach to known and unknown cases of Berge's conjecture

Berge's elegant dipath partition conjecture from 1982 states that in a dipath partition P of the vertex set of a digraph minimizing , there exists a collection Ck of k disjoint independent sets, where each dipath P?P meets exactly min{|P|, k} of the independent sets in C. This conjecture extends Linial's conjecture, the GreeneKleitman Theorem and Dilworth's Theorem for all digraphs. The conjecture is known to be true for acyclic digraphs. For general digraphs, it is known for k=1 by the GallaiMilgram Theorem, for k?? (where ?is the number of vertices in the longest dipath in the graph), by the GallaiRoy Theorem, and when the optimal path partition P contains only dipaths P with |P|?k. Recently, it was proved (Eur J Combin (2007)) for k=2. There was no proof that covers all the known cases of Berge's conjecture. In this article, we give an algorithmic proof of a stronger version of the conjecture for acyclic digraphs, using network flows, which covers all the known cases, except the case k=2, and the new, unknown case, of k=?-1 for all digraphs. So far, there has been no proof that unified all these cases. This proof gives hope for finding a proof for all k.

Estimation of the 2.0(5) helix type i -> i hydrogen bond energy at Aib*-Oxa motif: an isodesmic approach

Bending at the valence angle N-C-alpha-C' (tau) is a known control feature for attenuating the stability of the rare intramolecular hydrogen bonded pseudo five-membered ring C-5 structures, the so called 2.0(5) helices, at Aib. The competitive 3(10)-helical structures still predominate over the C5 structures at Aib for most values of tau. However at Aib*, a mimic of Aib where the carbonyl 0 of Aib is replaced with an imidate N (in 5,6-dihydro-4H-1,3-oxazine = Oxa), in the peptidomimic Piv-Pro-Aib*-Oxa (1), the C(5)i structure is persistent in both crystals and in solution. Here we show that the i -> i hydrogen bond energy is a more determinant control for the relative stability of the C5 structure and estimate its value to be 18.5 +/- 0.7 kJ/mol at Aib* in 1, through the computational isodesmic reaction approach, using two independent sets of theoretical isodesmic reactions. (C) 2014 Elsevier Ltd. All rights reserved.

Parameterized Algorithms for MAX COLORABLE INDUCED SUBGRAPH Problem on Perfect Graphs

We address the parameterized complexity ofMaxColorable Induced Subgraph on perfect graphs. The problem asks for a maximum sized q-colorable induced subgraph of an input graph G. Yannakakis and Gavril IPL 1987] showed that this problem is NP-complete even on split graphs if q is part of input, but gave a n(O(q)) algorithm on chordal graphs. We first observe that the problem is W2]-hard parameterized by q, even on split graphs. However, when parameterized by l, the number of vertices in the solution, we give two fixed-parameter tractable algorithms. The first algorithm runs in time 5.44(l) (n+#alpha(G))(O(1)) where #alpha(G) is the number of maximal independent sets of the input graph. The second algorithm runs in time q(l+o()l())n(O(1))T(alpha) where T-alpha is the time required to find a maximum independent set in any induced subgraph of G. The first algorithm is efficient when the input graph contains only polynomially many maximal independent sets; for example split graphs and co-chordal graphs. The running time of the second algorithm is FPT in l alone (whenever T-alpha is a polynomial in n), since q <= l for all non-trivial situations. Finally, we show that (under standard complexitytheoretic assumptions) the problem does not admit a polynomial kernel on split and perfect graphs in the following sense: (a) On split graphs, we do not expect a polynomial kernel if q is a part of the input. (b) On perfect graphs, we do not expect a polynomial kernel even for fixed values of q >= 2.

On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties

We study the problem of finding small s-t separators that induce graphs having certain properties. It is known that finding a minimum clique s-t separator is polynomial-time solvable (Tarjan in Discrete Math. 55:221-232, 1985), while for example the problems of finding a minimum s-t separator that induces a connected graph or forms an independent set are fixed-parameter tractable when parameterized by the size of the separator (Marx et al. in ACM Trans. Algorithms 9(4): 30, 2013). Motivated by these results, we study properties that generalize cliques, independent sets, and connected graphs, and determine the complexity of finding separators satisfying these properties. We investigate these problems also on bounded-degree graphs. Our results are as follows: Finding a minimum c-connected s-t separator is FPT for c=2 and W1]-hard for any ca parts per thousand yen3. Finding a minimum s-t separator with diameter at most d is W1]-hard for any da parts per thousand yen2. Finding a minimum r-regular s-t separator is W1]-hard for any ra parts per thousand yen1. For any decidable graph property, finding a minimum s-t separator with this property is FPT parameterized jointly by the size of the separator and the maximum degree. Finding a connected s-t separator of minimum size does not have a polynomial kernel, even when restricted to graphs of maximum degree at most 3, unless .

On Locally Gabriel Geometric Graphs

Let be a set of points in the plane. A geometric graph on is said to be locally Gabriel if for every edge in , the Euclidean disk with the segment joining and as diameter does not contain any points of that are neighbors of or in . A locally Gabriel graph(LGG) is a generalization of Gabriel graph and is motivated by applications in wireless networks. Unlike a Gabriel graph, there is no unique LGG on a given point set since no edge in a LGG is necessarily included or excluded. Thus the edge set of the graph can be customized to optimize certain network parameters depending on the application. The unit distance graph(UDG), introduced by Erdos, is also a LGG. In this paper, we show the following combinatorial bounds on edge complexity and independent sets of LGG: (i) For any , there exists LGG with edges. This improves upon the previous best bound of . (ii) For various subclasses of convex point sets, we show tight linear bounds on the maximum edge complexity of LGG. (iii) For any LGG on any point set, there exists an independent set of size .

Variations in the cyclotron resonant scattering features during 2011 outburst of 4U 0115+63

We study the variations in the Cyclotron Resonant Scattering Feature (CRSF) during 2011 outburst of the high mass X-ray binary 4U 0115+63 using observations performed with Suzaku, RXTE, Swift and INTEGRAL satellites. The wide-band spectral data with low-energy coverage allowed us to characterize the broad-band continuum and detect the CRSFs. We find that the broad-band continuum is adequately described by a combination of a low temperature (kT similar to 0.8 keV) blackbody and a power law with high energy cutoff (E-cut similar to 5.4 keV) without the need for a broad Gaussian at similar to 10 keV as used in some earlier studies. Though winds from the companion can affect the emission from the neutron star at low energies (<3 keV), the blackbody component shows a significant presence in our continuum model. We report evidence for the possible presence of two independent sets of CRSFs with fundamentals at similar to 11 and similar to 15 keV. These two sets of CRSFs could arise from spatially distinct emitting regions. We also find evidence for variations in the line equivalent widths, with the 11 keV CRSF weakening and the 15 keV line strengthening with decreasing luminosity. Finally, we propose that the reason for the earlier observed anticorrelation of line energy with luminosity could be due to modelling of these two independent line sets (similar to 11 and similar to 15 keV) as a single CRSF.

Stratigraphic Model Predictions of Geoacoustic Properties

Geoacoustic properties of the seabed have a controlling role in the propagation and reverberation of sound in shallow-water environments. Several techniques are available to quantify the important properties but are usually unable to adequately sample the region of interest. In this paper, we explore the potential for obtaining geotechnical properties from a process-based stratigraphic model. Grain-size predictions from the stratigraphic model are combined with two acoustic models to estimate sound speed with distance across the New Jersey continental shelf and with depth below the seabed. Model predictions are compared to two independent sets of data: 1) Surficial sound speeds obtained through direct measurement using in situ compressional wave probes, and 2) sound speed as a function of depth obtained through inversion of seabed reflection measurements. In water depths less than 100 m, the model predictions produce a trend of decreasing grain-size and sound speed with increasing water depth as similarly observed in the measured surficial data. In water depths between 100 and 130 m, the model predictions exhibit an increase in sound speed that was not observed in the measured surficial data. A closer comparison indicates that the grain-sizes predicted for the surficial sediments are generally too small producing sound speeds that are too slow. The predicted sound speeds also tend to be too slow for sediments 0.5-20 m below the seabed in water depths greater than 100 m. However, in water depths less than 100 m, the sound speeds between 0.5-20-m subbottom depth are generally too fast. There are several reasons for the discrepancies including the stratigraphic model was limited to two dimensions, the model was unable to simulate biologic processes responsible for the high sound-speed shell material common in the model area, and incomplete geological records necessary to accurately predict grain-size