97,750 research outputs found
Fixed-Parameter Tractability of the Weighted Edge Clique Partition Problem
No full textWe develop an FPT algorithm and a compression for the Weighted Edge Clique Partition (WECP) problem, where a graph with n vertices and integer edge weights is given together with an integer k, and the aim is to find k cliques, such that every edge appears in exactly as many cliques as its weight. The problem has been previously only studied in the unweighted version called Edge Clique Partition (ECP), where the edges need to be partitioned into k cliques. It was shown that ECP admits a kernel with k² vertices [Mujuni and Rosamond, 2008], but this kernel does not extend to WECP. The previously fastest algorithm known for ECP has a runtime of 2^(k²)n^O(1) [Issac, 2019]. For WECP we develop a compression (to a slightly more general problem) with 4^k vertices, and an algorithm with runtime 2^(k^(3/2)w^(1/2)log(k/w))n^O(1), where w is the maximum edge weight. The latter in particular improves the runtime for ECP to 2^(k^(3/2)log k)n^O(1)
Joshua Davis: Author of Spare Parts
No full textCitation: K-State First (2016). Joshua Davis: Author of Spare Parts [Flier]. Manhattan, Kansas: K-State First.Flyer advertising Joshua Davis's author talk at Kansas State University
Records of the Manhattan Town Association, commencing Jan. 9th 1856 to ... : also a copy of the constitution and by laws. Book Two.
No full textC.E. Blood, J.D. Woodworth, and Issac Goodnow recording secretaries
Steven Johnson Author Talk Poster
No full textK-State Book NetworkA poster advertising an author talk by Steven Johnson at Kansas State University on September 3, 2014. Steven Johnson's book "The Ghost Map" was the 2014-2015 common book
On the Parameterized Complexity of Biclique Cover and Partition
No full textGiven a bipartite graph G, we consider the decision problem called BicliqueCover for a fixed positive integer parameter k where we are asked whether the edges of G can be covered with at most k complete bipartite subgraphs (a.k.a. bicliques). In the BicliquePartition problem, we have the additional constraint that each edge should appear in exactly one of the k bicliques. These problems are both known to be NP-complete but fixed parameter tractable. However, the known FPT algorithms have a running time that is doubly exponential in k, and the best known kernel for both problems is exponential in k. We build on this kernel and improve the running time for BicliquePartition to O*(2^{2k^2+k*log(k)+k}) by exploiting a linear algebraic view on this problem. On the other hand, we show that no such improvement is possible for BicliqueCover unless the Exponential Time Hypothesis (ETH) is false by proving a doubly exponential lower bound on the running time. We achieve this by giving a reduction from 3SAT on n variables to an instance of BicliqueCover with k=O(log(n)). As a further consequence of this reduction, we show that there is no subexponential kernel for BicliqueCover unless P=NP. Finally, we point out the significance of the exponential kernel mentioned above for the design of polynomial-time approximation algorithms for the optimization versions of both problems. That is, we show that it is possible to obtain approximation factors of n/log(n) for both problems, whereas the previous best approximation factor was n/sqrt(log(n))
Connected k-Partition of k-Connected Graphs and c-Claw-Free Graphs
No full textA connected partition is a partition of the vertices of a graph into sets that induce connected subgraphs. Such partitions naturally occur in many application areas such as road networks, and image processing. In these settings, it is often desirable to partition into a fixed number of parts of roughly of the same size or weight. The resulting computational problem is called Balanced Connected Partition (BCP). The two classical objectives for BCP are to maximize the weight of the smallest, or minimize the weight of the largest component. We study BCP on c-claw-free graphs, the class of graphs that do not have K_{1,c} as an induced subgraph, and present efficient (c-1)-approximation algorithms for both objectives. In particular, for 3-claw-free graphs, also simply known as claw-free graphs, we obtain a 2-approximation. Due to the claw-freeness of line graphs, this also implies a 2-approximation for the edge-partition version of BCP in general graphs.
A harder connected partition problem arises from demanding a connected partition into k parts that have (possibly) heterogeneous target weights w₁,…,w_k. In the 1970s Győri and Lovász showed that if G is k-connected and the target weights sum to the total size of G, such a partition exists. However, to this day no polynomial algorithm to compute such partitions exists for k > 4. Towards finding such a partition T₁,…, T_k in k-connected graphs for general k, we show how to efficiently compute connected partitions that at least approximately meet the target weights, subject to the mild assumption that each w_i is greater than the weight of the heaviest vertex. In particular, we give a 3-approximation for both the lower and the upper bounded version i.e. we guarantee that each T_i has weight at least (w_i)/3 or that each T_i has weight most 3w_i, respectively. Also, we present a both-side bounded version that produces a connected partition where each T_i has size at least (w_i)/3 and at most max({r,3}) w_i, where r ≥ 1 is the ratio between the largest and smallest value in w₁, … , w_k. In particular for the balanced version, i.e. w₁ = w₂ = , … , = w_k, this gives a partition with 1/3w_i ≤ w(T_i) ≤ 3w_i
Going Beyond Counting First Authors in Author Co-citation Analysis
No full textThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
The effect of crack-tip interactions on the curve-fitting of mixed-mode isopachics
No full textThermoelastic Stress Analysis (TSA) is a full-field technique for experimental stress analysis that has proved to be extremely effective for studying stress fields in the vicinity of crack-tips. An understanding of such fields is vital to the development of effective diagnosis and prognosis algorithms for Non-Destructive Testing (NDT) and Structural Health Monitoring (SHM). The key to crack-tip studies using TSA is the observation that the stress-sum contours (isopachics) in the vicinity of the tip take the form of a simple curve – the cardioid. This was exploited in [1] in order to estimate the Stress Intensity Factors (SIFs) for crack-tips in mode 1 and mixed-mode opening. The analysis [1] made use of the cardioid nature of the isopachics by deriving expressions for the SIFs in terms of the cardioid area and the positions of certain tangents to the curve.Recent work by the authors has allowed the estimation of crack-tip Stress Intensity Factors (SIFs) by curve-fitting a cardioid form to measured isopachics from Thermoelastic Stress Analysis (TSA). Both Genetic Algorithms (GAs) [2] and Differential Evolution (DE) [3] proved successful for the actual parameter estimation, but some of the curve-fits indicated that the cardioid form was inappropriate for the base model. A possible explanation for the poor curve-fit is that the cardioid form is only theoretically suitable for an isolated crack-tip stress field, as derived from the Westergaard equations. The effect of the other crack-tip in a central crack hac been neglected from previous analyses. Further work has [4] considered a mode 1 central crack, placed in a plate, which therefore had two interacting crack-tips. Figure 1 shows the analytically derived stress sum field around both an isolated mode 1 crack and a twin crack-tip. The curves for an isolated crack-tip are shown as solid lines – these curves are true cardioids. The curves for the twin crack-tip case are shown as dashed lines. It is clear that these curves are not cardioids, although the level of distortion is quite small for the inner curves. The object of the current paper is to determine numerically, the stress field for a mixed-mode crack system and to quantify the effect of any interactions on the curve-fitting procedure and compare with experimental data for a 30o crack
Appropriate Similarity Measures for Author Cocitation Analysis
No full textWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Expanding “Communities and Collections” in the K-State Research Exchange (K-REx) to benefit the K-State Community and Beyond
No full textKansas State University has used its institutional repository, the K-State Research Exchange (K-REx), to store and share its first year experience program, K-State First, and notably its common reading program, K-State First Book. We have done so with the aim that the accessibility and preservation of these documents ensures program stability, promotes engagement with first year programming, and provides the ability to foster growth,educational opportunities, and community building outside of K-State. Moving away from research concentrated repositories and taking a more holistic approach to scholarship, especially when realizing the pedagogical significance of collaborative campus programming, institutions can showcase, discover, preserve, and grow programs that shape campus communities and engagement.
This session will provide an overview of K-REx and spotlight the digital archive of the university’s first year experience program and common reading program, K-State First Book. We will discuss the benefits and challenges to expanding the purview of your repositories. We talkthrough the types of materials we decide to host in our repository and why we share what we do. We will also provide recommendations on new ways to evaluate what belongs in institutional repositories and how this diversity can benefit your program, your institution, the community, and others
- …
