120,175 research outputs found
New insights in high-energy electron emission and underlying transport physics of nanocrystalline Si
No full textJoshua 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
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
Electron Energy Loss Behavior in Si Quantum Dots Interconnected with Tunnel Oxide Barriers
No full textEfficient enumeration of maximal k-degenerate induced subgraphs of a chordal graph
No full textIn this paper we consider the problem of listing the maximal k-degenerate induced subgraphs of a chordal graph, and propose an output-sensitive algorithm using delay O(m⋅ω(G)) for any n-vertex chordal graph with m edges, where ω(G)≤n is the maximum size of a clique in G. Degeneracy is a well known sparsity measure, and k-degenerate subgraphs are a notion of sparse subgraphs, which generalizes other problems such as independent sets (0-degenerate subgraphs) and forests (1-degenerate subgraphs). Many efficient enumeration algorithms are designed by solving the so-called Extension problem, which asks whether there exists a maximal solution containing a given set of nodes, but no node from a forbidden set. We show that solving this problem is NP-complete for maximal k-degenerate induced subgraphs, motivating the need for additional techniques
In honor of Philip M. Morse.
No full textIncludes bibliographies.Editors Herman Feshbach and K. Uno Ingard
Opening Access: Increasing Scholarly Impact with DigitalCommons@UNO
No full textDigitalCommons@UNO (https://digitalcommons.unomaha.edu/) is an Institutional Repository (IR) and an initiative implemented by the University of Nebraska at Omaha (UNO) Libraries to support our UNO scholars through providing a Green Open Access solution. DigitalCommons@UNO disseminates a wide variety of scholarship including faculty papers, electronic theses and dissertations (ETDs), conferences and journals. Since its launch in 2014, the UNO Libraries have been implementing and managing DigitalCommons@UNO through outreach to the UNO community in an effort to collect scholarly works into the IR
New polynomial delay bounds for maximal subgraph enumeration by proximity search
No full textIn this paper we propose polynomial delay algorithms for several maximal subgraph listing problems, by means of a seemingly novel technique which we call proximity search. Our result involves modeling the space of solutions as an implicit directed graph called “solution graph”, a method common to other enumeration paradigms such as reverse search. Such methods, however, can become inefficient due to this graph having vertices with high (potentially exponential) degree. The novelty of our algorithm consists in providing a technique for generating better solution graphs, reducing the out-degree of its vertices with respect to existing approaches, and proving that it remains strongly connected. Applying this technique, we obtain polynomial delay listing algorithms for several problems for which output-sensitive results were, to the best of our knowledge, not known. These include Maximal Bipartite Subgraphs, Maximal k-Degenerate Subgraphs (for bounded k), Maximal Induced Chordal Subgraphs, and Maximal Induced Trees. We present these algorithms, and give insight on how this general technique can be applied to other problems
- …
