• Piri Keşif Aracı

Arama ipuçları nelerdir?
1.  sayfa ve
1
Parameterized pursuit-evasion games
Dergi Makalesi

Dergi Makalesi
Kaynak :
Science Direct
Dergi:
Theoretical Computer Science
Yayıncı:
Elsevier
Yazar(lar) :
Allan Scott , Ulrike Stege
Yıl :
2010
Ulrike Stege
Yayıncı Web Sitesi
Tam Metin
Kaydet Alıntıla
We study the parameterized complexity of four variants of pursuit-evasion on graphs: Seeded Pursuit Evasion, Short Seeded Pursuit Evasion, Directed Pursuit Evasion and Short Directed Pursuit Evasion. Both Seeded Pursuit Evasion and Short Seeded Pursuit Evasion are played on undirected graphs with given starting positions for both the cops and the robber. Directed Pursuit Evasion and its short variant are played on directed graphs, with the players free to choose their starting positions. We show for Seeded Pursuit Evasion and Directed Pursuit Evasion that finding a winning strategy for the cops is AW[*]-hard when we parameterize by the number of cops. Further, we show that the short ( k-move) variants of these problems (Short Seeded Pursuit Evasion and Short Directed Pursuit Evasion) are AW[*]-complete when we parameterize by both the number of cops and turns.
DOI : 10.1016/j.tcs.2010.07.004
Anahtar Kelimeler : Parameterized complexity, Cops and robber, Algorithmic combinatorial game theory
ISSN: 0304-3975
Sayı: 43
Cilt: 411
Sayfa: 3845-3858
Sınıflandırma :
2
A Provably, Linear Time, In-place and Stable Merge Algorithm via the Perfect Shuffle
Araştırma Makalesi

Araştırma Makalesi
Open Access
Kaynak :
arXiv
Yazar(lar) :
John Ellis , Ulrike Stege
Konu :
Data Structures and Algorithms
Yıl :
2015
Ulrike Stege
Yayıncı Web Sitesi
Tam Metin
Kaydet Alıntıla
We reconsider a recently published algorithm (Dalkilic et al.) for merginglists by way of the perfect shuffle. The original publication gave onlyexperimental results which, although consistent with linear execution time onthe samples tested, provided no analysis. Here we prove that the timecomplexity, in the average case, is indeed linear, although there is anOmega(n^2) worst case. This is then the first provably linear time mergealgorithm based on the use of the perfect shuffle. We provide a proof ofcorrectness, extend the algorithm to the general case where the lists are ofunequal length and show how it can be made stable, all aspects not included inthe original presentation and we give a much more concise definition of thealgorithm.
3
Analogs & duals of the MAST problem for sequences & trees
Dergi Makalesi

Dergi Makalesi
Kaynak :
Science Direct
Dergi:
Journal of Algorithms
Yayıncı:
Elsevier
Yazar(lar) :
Michael Fellows , Michael Hallett , Ulrike Stege
Yıl :
2003
Ulrike Stege
Yayıncı Web Sitesi
Tam Metin
Kaydet Alıntıla
Two natural kinds of problems about “structured collections of symbols” can be generally referred to as the Largest Common Subobject and the Smallest Common Superobject problems, which we consider here as the dual problems of interest. For the case of rooted binary trees where the symbols occur as leaf-labels and a subobject is defined by label-respecting hereditary topological containment, both of these problems are NP-complete, as are the analogous problems for sequences (the well-known Longest Common Subsequence and Shortest Common Supersequence problems). When the trees are restricted by allowing each symbol to occur as a leaf-label at most once (which we call a phylogenetic tree or p-tree), then the Largest Common Subtree problem, better known as the Maximum Agreement Subtree (MAST) problem, is solvable in polynomial time. We explore the complexity of the basic subobject and superobject problems for both sequences and binary trees when the inputs are restricted to p-trees and p-sequences (p-sequences are sequences where each symbol occurs at most once). We prove that the sequence analog of MAST can be solved in polynomial time. The Shortest Common Supersequence problem restricted to inputs consisting of a collection of p-sequences (pSCS) is NP-complete; we show NP-completeness of the analogous Smallest Common Supertree problem restricted to p-trees (pSCT). We also show that both problems are hard for the parameterized complexity classes W[1] where the parameter is the number of input objects. We prove fixed-parameter tractability for pSCS and pSCT when the k input objects are restricted to be complete: every symbol of Σ occurs exactly once in each object and the question is whether there is a common superobject of size bounded by |Σ|+r and the parameter is the pair (k,r). We show that without this restriction, both problems are harder than Directed Feedback Vertex Set, for which parameterized complexity is famously unresolved.
DOI : 10.1016/s0196-6774(03)00081-6
ISSN: 0196-6774
Sayı: 1
Cilt: 49
Sayfa: 192-216
4
k-Attribute-Anonymity is hard even for k=2
Dergi Makalesi

Dergi Makalesi
Kaynak :
Science Direct
Dergi:
Information Processing Letters
Yayıncı:
Elsevier
Yazar(lar) :
Allan Scott , Venkatesh Srinivasan , Ulrike Stege
Yıl :
2015
Ulrike Stege
Yayıncı Web Sitesi
Tam Metin
Kaydet Alıntıla
We study the problem of anonymizing data by column suppression. Meyerson and Williams showed that this problem is NP-hard for k≥3. The complexity of this problem for k=2 remained open. In this note, we show that 2-anonymizing data by suppressing the minimum number of columns is also NP-hard. In fact, we prove a stronger claim that this problem is NP-hard to approximate within a factor of Ω(log⁡m), where m is the number of columns in the table. Furthermore, our proof also shows that this problem, parameterized by the number of columns to be suppressed, is not in FPT unless W[2]=FPT.
DOI : 10.1016/j.ipl.2014.10.011
Anahtar Kelimeler : Computational complexity, Database privacy, Data anonymization, Fixed parameter tractability, NP-hardness
ISSN: 0020-0190
Sayı: 2
Cilt: 115
Sayfa: 368-370
Sınıflandırma :
5
Suffix trees for inputs larger than main memory
Dergi Makalesi

Dergi Makalesi
Kaynak :
Science Direct
Dergi:
Information Systems
Yayıncı:
Elsevier
Yazar(lar) :
Marina Barsky , Ulrike Stege , Alex Thomo
Yıl :
2011
Ulrike Stege
Yayıncı Web Sitesi
Tam Metin
Kaydet Alıntıla
A suffix tree is a fundamental data structure for string searching algorithms. Unfortunately, when it comes to the use of suffix trees in real-life applications, the current methods for constructing suffix trees do not scale for large inputs. As suffix trees are larger than the input sequences and quickly outgrow the main memory, the first attempts at building large suffix trees focused on algorithms which avoid massive random access to the trees being built. However, all the existing practical algorithms perform random access to the input string, thus requiring in essence that the input be small enough to be kept in main memory. The constantly growing pool of string data, especially biological sequences, requires us to build suffix trees for much larger strings. We are the first to present an algorithm which is able to construct suffix trees for input sequences significantly larger than the size of the available main memory. Both the input string and the suffix tree are kept on disk and the algorithm is designed to avoid multiple random I/Os to both of them.1 As a proof of concept, we show that our method allows to build the suffix tree for 12 GB of real DNA sequences in 26 h on a single machine with 2 GB of RAM. This input is four times the size of the Human Genome, and the construction of suffix trees for inputs of such magnitude was never reported before.
DOI : 10.1016/j.is.2010.11.001
Anahtar Kelimeler : String databases, Suffix trees, Full-text indexes
ISSN: 0306-4379
Sayı: 3
Cilt: 36
Sayfa: 644-654
Sınıflandırma :
6
Sources of complexity in subset choice
Dergi Makalesi

Dergi Makalesi
Kaynak :
Science Direct
Dergi:
Journal of Mathematical Psychology
Yayıncı:
Elsevier
Yazar(lar) :
Iris van Rooij , Ulrike Stege , Helena Kadlec
Yıl :
2005
Ulrike Stege
Yayıncı Web Sitesi
Tam Metin
Kaydet Alıntıla
Subset choice denotes the task of choosing a subset of items from among a set of available items. Because the number of possible choice options in subset choice grows exponentially with the size of the choice set, subset choice tasks can be computationally challenging. This paper discusses how the computational complexity of subset choice under different models can be utilized in the quest for descriptive models of subset choice. We consider several models of subset choice (including the additive model, the binary-interaction model and the h-ary interaction model) and show how the theory of computational complexity (including the theory of NP-completeness and fixed-parameter tractability) can be used to evaluate the psychological plausibility of such models under different assumptions of processing speed, parallelism and size of problem parameters.
DOI : 10.1016/j.jmp.2005.01.002
Anahtar Kelimeler : Subset choice, Computational complexity, Decision-making, NP-completeness, Intractability, Fixed-parameter tractable, Algorithms
ISSN: 0022-2496
Sayı: 2
Cilt: 49
Sayfa: 160-187
Sınıflandırma :
7
A Framework for Classification of Resource Consolidation Management Problems
Konferans Bildirileri

Konferans Bildirileri
Kaynak :
IEEE Xplore
Yazar(lar) :
Steven Lonergan , Yagiz Onat Yazir , Ulrike Stege
Konu :
Communication, Networking and Broadcast Technologies, Components, Circuits, Devices and Systems, Computing and Processing
Yıl :
2012
Ulrike Stege
Yayıncı Web Sitesi
Tam Metin
Kaydet Alıntıla
Much effort in the current literature has been put towards methods and implementations to solve Resource Consolidation Management (RCM) problems in the cloud setting. A vast number of proposed solutions appears to be designed for different variants of the RCM problem. This makes the comparison of approaches challenging. We propose a new framework that facilitates mapping RCM solutions to their RCM problem definitions. Our framework allows a solution to be assigned to its RCM problem definition by means of answering a set of questions specific to RCM problems. Our framework can be used to (1) specify problem descriptions, (2) establish optimal solutions and providing theoretical benchmarks, (3) provide a platform allowing formal complexity analysis of RCM problems and (4) facilitate a healthy discussion about the essence of RCM and evaluations of different solutions. We show how our proposed framework can be applied in form of case studies depicting four approaches from the literature.
DOI : 10.1109/cloud.2012.114
Anahtar Kelimeler : Uncertainty, Cloud computing, Computer science, Educational institutions, Electronic mail, Resource management, cloud computing, formal concept analysis, pattern classification, resource allocation, resource consolidation management problem, RCM problem, cloud setting, RCM solution mapping, RCM problem definition, problem description, formal complexity analysis, classification framework, cloud computing, resource consolidation management, theoretical benchmarks, unified framework
8
Quantum Computing for High-School Students An Experience Report
Konferans Bildirileri

Konferans Bildirileri
Kaynak :
IEEE Xplore
Yazar(lar) :
Prashanti Priya Angara , Ulrike Stege , Andrew MacLean
Konu :
Communication, Networking and Broadcast Technologies, Components, Circuits, Devices and Systems, Computing and Processing, Engineering Profession, Photonics and Electrooptics
Yıl :
2020
Ulrike Stege
Yayıncı Web Sitesi
Tam Metin
Kaydet Alıntıla
Quantum computing is an emerging field that can revolutionize our ability to solve problems and enable breakthroughs in many areas including optimization, machine learning, chemistry, and drug design. With the increasing computational power of quantum computers and the proliferation of quantum development kits, the demand for a skilled workforce in quantum computing increases significantly. The theory of quantum computing lies at the crossroads of quantum physics, mathematics, and computer science. The field of quantum computing has matured and can now be explored by all students. While today, quantum computers and simulators are readily accessible and programmable over the internet, quantum computing education is just ramping up. This paper describes our experiences in organizing and delivering quantum computing workshops for high-school students with little or no experience in the abovementioned fields. We introduce students to the world of quantum computing in innovative ways, such as newly designed “unplugged” activities for teaching basic quantum computing concepts. Overall, we take a programmatic approach and introduce students to the IBM Q Experience using Qiskit and Jupyter notebooks. Our experiences and findings suggest that basic quantum computing concepts are palatable for high-school students, and-due to significant differences between classical and quantum computing-early exposure to quantum computing is a valuable addition to the set of problem-solving and computing skills that high-schoolers obtain before entering university.
DOI : 10.1109/qce49297.2020.00047
Anahtar Kelimeler : Quantum computing, Quantum mechanics, Games, Qubit, Conferences, Programming profession, Training, computer aided instruction, computer science education, educational courses, educational institutions, Internet, quantum computing, teaching, high-school students, quantum computers, quantum computing education, basic quantum computing concepts, IBM Q Experience, Qiskit notebook, Jupyter notebook, Quantum computing, education, training, high schoolers, teachers, workforce development, CS-unplugged, qubit systems, quantum gates, measurement, superposition, entanglement, quantum teleportation, Qiskit, quantum computing games
Sınıflandırma :
9
Information Brokers in Requirement-Dependency Social Networks
Konferans Bildirileri

Konferans Bildirileri
Kaynak :
IEEE Xplore
Yazar(lar) :
Sabrina Marczak , Daniela Damian , Ulrike Stege , Adrian Schröter
Konu :
Components, Circuits, Devices and Systems, Engineered Materials, Dielectrics and Plasmas
Yıl :
2008
Ulrike Stege
Yayıncı Web Sitesi
Tam Metin
Kaydet Alıntıla
Requirements interdependencies create technical dependencies among project members that generally belong to different functional groups in an organization, but who need to coordinate activities during processes of requirements change management. Effective knowledge management is needed to disseminate information on requirement changes across teams working on interdependent requirements to avoid mis-interpretations. Social networks are regarded as important in fostering knowledge management, where brokers or gatekeepers have the role of project members facilitating information flow. However, little is known about processes of information flow and brokerage in social networks built around interdependent requirements. In a field study of requirement interdependencies in a large IT manufacturing organization, we found that brokers holding pockets of knowledge have an impact on information flow in requirement-interdependent teams. We discuss a number of patterns of information flow and draw implications for processes of requirements change management.
DOI : 10.1109/re.2008.26
Anahtar Kelimeler : knowledge management, social sciences, information brokers, requirement-dependency social networks, requirements interdependencies, technical dependencies, effective knowledge management, Change management, Requirements dependencies, Social networks, Information flow, Information brokers
10
Shortest Path Approaches for the Longest Common Subsequence of a Set of Strings
Konferans Bildirileri

Konferans Bildirileri
Kaynak :
IEEE Xplore
Yazar(lar) :
Marina Barsky , Ulrike Stege , Alex Thomo , Chris Upton
Konu :
Bioengineering, Computing and Processing
Yıl :
2007
Ulrike Stege
Yayıncı Web Sitesi
Tam Metin
Kaydet Alıntıla
We investigate the k-LCS problem that is finding a longest common subsequence (LCS) for k given input strings. The problem is known to have practical solutions for k = 2, but for higher dimensions it is not very well explored. We consider the algorithms by Miller and Myers as well as Wu et al. which solve the 2-LCS problem, and shed a new light on their generalization to higher dimensions. First, we redesign both algorithms such that the generalization to higher dimensions becomes natural. Then we present our algorithms for solving the k-LCS problem. We further propose a new approach to reduce the algorithms' space complexity. We demonstrate that our algorithms are practical as they significantly outperform the dynamic programming approaches. Our results stand in contrast to observations made in previous work by Irving and Fraser.
DOI : 10.1109/bibe.2007.4375584
Anahtar Kelimeler : Sequences, Computer science, Bioinformatics, RNA, Dynamic programming, Biochemistry, Biochemical analysis, Biology computing, DNA computing, Heuristic algorithms, computational complexity, dynamic programming, sequences, string matching, longest common subsequence, k-LCS problem, input strings, Miller-and-Myers algorithms, dynamic programming approach, shortest path approach
11
SARS-CoV-2 Ribosomal Frameshifting Pseudoknot: Detection of Inter-viral Structural Similarity
Konferans Bildirileri

Konferans Bildirileri
Kaynak :
IEEE Xplore
Yazar(lar) :
Luke Trinity , Lance Lansing , Hosna Jabbari , Ulrike Stege
Konu :
Computing and Processing
Yıl :
2021
Ulrike Stege
Yayıncı Web Sitesi
Tam Metin
Kaydet Alıntıla
Severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) has led to the COVID-19 pandemic. After over 160 million cases and 3.3 million deaths worldwide as of May 2021, it is still unclear when this crisis will end. Thus, there is an urgent need for treatments that improve the prognosis of seriously affected patients. Multiple viruses including HIV, MERS-CoV (coronavirus responsible for Middle East Respiratory Syndrome, MERS), SARS-CoV (coronavirus responsible for SARS) and SARS-CoV-2 use a mechanism known as -1 programmed ribosomal frameshifting (-1 PRF) to successfully replicate. SARS-CoV and SARS-CoV-2 possess a unique RNA pseudoknotted structure that stimulates -1 PRF. Recent experiments identified small molecules as antiviral agents that can bind to the pseudoknot and disrupt its stimulation of -1 PRF. Targeting -1 PRF in SARS-CoV-2 can be an excellent strategy to impair viral replication and improve patients’ prognoses. Crucial to developing these successful therapies is modeling the structure of the SARS-CoV-2 -1 PRF pseudoknot. Following a structural alignment approach, we identify similarities in -1 PRF pseudoknots of SARS-CoV-2, SARS-CoV, and MERS-CoV. In addition, we provide a better understanding of the SARS-CoV-2 -1 PRF pseudoknot by investigating the structural landscape using a hierarchical folding approach. We provide in-depth analysis on alternative structure prediction methods based on SARS-CoV-2 structural reactivity (SHAPE) data to contextualize and motivate future RNA structure-function research. Since understanding the impact of mutations is vital to long-term success of treatments based on predicted RNA functional structures, we provide insight on SARS-CoV-2 -1 PRF pseudoknot sequence mutations and their effect on the resulting structure.
DOI : 10.1109/ichi52183.2021.00080
Anahtar Kelimeler : COVID-19, Solid modeling, Shape, Pandemics, RNA, Medical treatment, Predictive models, diseases, epidemics, genetics, microorganisms, molecular biophysics, molecular configurations, proteins, RNA, SHAPE data, RNA pseudoknotted structure, 1 programmed ribosomal frameshifting, Middle East Respiratory Syndrome, HIV, COVID-19 pandemic, interviral structural similarity, SARS-CoV-2 structural reactivity, MERS-CoV, severe acute respiratory syndrome coronavirus 2, SARS-CoV-2 ribosomal frameshifting pseudoknot, SARS-CoV-2 -1 PRF pseudoknot sequence mutations, secondary structure, prf stimulating pseudoknot, frameshifting, COVID-19, variants, structural alignment
12
Minesweeper May Not Be NP-Complete but Is Hard Nonetheless
Dergi Makalesi

Dergi Makalesi
Kaynak :
Springer Link
Dergi:
The Mathematical Intelligencer
Yazar(lar) :
Allan Scott , Ulrike Stege , Iris van Rooij
Konu :
History and Philosophy of Science, General Mathematics
Yıl :
2011
Ulrike Stege
Yayıncı Web Sitesi
Tam Metin
Kaydet Alıntıla
DOI : 10.1007/s00283-011-9256-x
Anahtar Kelimeler : Polynomial Time, Mathematical Intelligencer, Conjunctive Normal Form, Truth Assignment, Boolean Formula
ISSN: 0343-6993 1866-7414
Sayı: 4
Cilt: 33
Sayfa: 5-17
Sınıflandırma :
Felsefe %48
Mantık %100
13
Resolving conflicts in problems from computational biology
Tez

Tez
Open Access
Kaynak :
The Dart-Europe
Dergi:
ETH Zurich
Yazar(lar) :
Ulrike Stege
Yıl :
1999
Ulrike Stege
Yayıncı Web Sitesi
Kaydet Alıntıla
14
Linear programming applied to polarized Raman spectroscopy for elucidating molecular structure at surfaces
Dergi Makalesi

Dergi Makalesi
Kaynak :
Science Direct
Dergi:
Chemometrics and Intelligent Laboratory Systems
Yayıncı:
Elsevier
Yazar(lar) :
Fei Chen , Kuo-Kai Hung , Dennis K. Hore , Ulrike Stege
Yıl :
2020
Ulrike Stege
Yayıncı Web Sitesi
Tam Metin
Kaydet Alıntıla
We present a framework for using linear programming to solve a challenging problem in surface science, the elucidation of the structure and composition of adsorbed molecules from a mixture, using simulated data from polarized Raman experiments. In the past, methods applied in order to interpret such spectroscopic information were combinatorial approaches that are limited in scalability or accuracy. Quantum mechanical electronic structure calculations yield the optical response of a single molecule, from which spectra of a mixture can be determined by appropriate weighting. Furthermore, spectral obtained in different beam polarizations provide projections of the signal in the laboratory frame. We demonstrate that linear programming is an ideal tool for utilizing all of this information in order to provide the sought structural picture.
DOI : 10.1016/j.chemolab.2019.103898
Anahtar Kelimeler : Linear programming, Molecular structure, Vibrational spectroscopy
ISSN: 0169-7439
Cilt: 196
Sayfa: 103898
Sınıflandırma :
15
How do biological networks differ from social networks? (an experimental study)
Konferans Bildirileri

Konferans Bildirileri
Kaynak :
IEEE Xplore
Yazar(lar) :
Tatiana Gutierrez-Bunster , Ulrike Stege , Alex Thomo , John Taylor
Konu :
Computing and Processing
Yıl :
2014
Ulrike Stege
Yayıncı Web Sitesi
Tam Metin
Kaydet Alıntıla
In this paper we outline important differences between (1) protein interaction networks and (2) social and other complex networks, in terms of fine-grained network community profiles. While these families of networks present some general similarities, they also have some stark differences in the way the communities are formed. Namely, we find that the sizes of the best communities in such biological networks are an order of magnitude smaller than in social and other complex networks. We furthermore find that the generative model describing biological networks is very different from the model describing social networks. While for latter the Forest-Fire model best approximates their network community profile, for biological networks it is a random rewiring model that generates networks with the observed profiles. Our study suggests that these families of networks should be treated differently when deriving results from network analysis, and a fine-grained analysis is needed to better understand their structure.
DOI : 10.1109/asonam.2014.6921669
Anahtar Kelimeler : Communities, Social network services, Proteins, Biological system modeling, Clustering algorithms, Conferences, bioinformatics, social networking (online), random rewiring model, network community profile, forest-fire model, generative model, fine-grained network community profiles, complex networks, protein interaction networks, social networks, biological networks
Sınıflandırma :
16
IR Absorption, Raman Scattering, and IR-Vis Sum-Frequency Generation Spectroscopy as Quantitative Probes of Surface Structure
Dergi Makalesi

Dergi Makalesi
Kaynak :
Taylor and Francis
Dergi:
Applied Spectroscopy Reviews
Yayıncı:
Informa UK Limited
Yazar(lar) :
Kuo-Kai Hung , Ulrike Stege , Dennis K. Hore
Yıl :
2014
Ulrike Stege
Yayıncı Web Sitesi
Tam Metin
Kaydet Alıntıla
:Vibrational spectroscopy is a valuable quantitative tool for the determination of structure at surfaces. Various techniques may be applicable and useful, depending on what is available, the transparency of the substrates, the need for in situ probes, and the degree of interfacial specificity required. We examine and compare signals in infrared absorption, Raman scattering, and vibrational sum-frequency generation spectroscopy to the underlying molecular response. In all of these experiments, varying the beam polarizations enables the orientation of specific chemical functional groups to be determined. However, the sensitivity of each technique is directly connected to the manner in which the molecular response manifests itself in the measured signal. Starting with simple distributions of a single vibrational mode, leading up to multiple vibrational bands in more complex orientation distributions, we compare these three techniques in terms of their sensitivity to features of the molecular orientation distribution. This review is aimed at guiding planned experiments when multiple techniques are available for surface structural analysis.
DOI : 10.1080/05704928.2014.986736
Anahtar Kelimeler : Molecular orientation, surface structure, infrared absorption, Raman Scattering, visible-infrared sum-frequency generation
ISSN: 0570-4928
Sayı: 4
Cilt: 50
Sayfa: 351-376
17
Solving large FPT problems on coarse-grained parallel machines
Dergi Makalesi

Dergi Makalesi
Kaynak :
Science Direct
Dergi:
Journal of Computer and System Sciences
Yayıncı:
Elsevier
Yazar(lar) :
James Cheetham , Frank Dehne , Andrew Rau-Chaplin , Ulrike Stege , Peter J. Taillon
Yıl :
2003
Ulrike Stege
Yayıncı Web Sitesi
Tam Metin
Kaydet Alıntıla
Fixed-parameter tractability (FPT) techniques have recently been successful in solving NP-complete problem instances of practical importance which were too large to be solved with previous methods. In this paper, we show how to enhance this approach through the addition of parallelism, thereby allowing even larger problem instances to be solved in practice. More precisely, we demonstrate the potential of parallelism when applied to the bounded-tree search phase of FPT algorithms. We apply our methodology to the k-Vertex Cover problem which has important applications in, for example, the analysis of multiple sequence alignments for computational biochemistry. We have implemented our parallel FPT method for the k-Vertex Cover problem using C and the MPI communication library, and tested it on a 32-node Beowulf cluster. This is the first experimental examination of parallel FPT techniques. As part of our experiments, we solved larger instances of k-Vertex Cover than in any previously reported implementations. For example, our code can solve problem instances with k⩾400 in less than 1.5h.
DOI : 10.1016/s0022-0000(03)00075-8
ISSN: 0022-0000
Sayı: 4
Cilt: 67
Sayfa: 691-706
Sınıflandırma :
18
2D correlation analysis in vibrational sum-frequency generation spectroscopy
Dergi Makalesi

Dergi Makalesi
Kaynak :
Science Direct
Dergi:
Journal of Molecular Structure
Yayıncı:
Elsevier
Yazar(lar) :
Sandra Roy , Joshua S. Post , Kuo-Kai Hung , Ulrike Stege , Dennis K. Hore
Yıl :
2014
Ulrike Stege
Yayıncı Web Sitesi
Tam Metin
Kaydet Alıntıla
2D correlation analysis provides a powerful means of extracting structural and dynamical data from spectroscopic experiments. This has been successfully developed for techniques such as IR absorption spectroscopy, where the correlation has additionally been shown to increase the spectral resolution by observing the differing behavior of overlapping absorption bands in response to an external perturbation. Visible-infrared sum-frequency generation (SFG) spectroscopy combines many of the benefits of IR absorption and Raman scattering spectroscopy, and adds a unique structural perspective due to its surface specificity. Bringing the flexibility of 2D correlation analysis to SFG experiments would therefore further enhance the power and utility of this nonlinear vibrational spectroscopy. However, straightforward application of the correlation algorithms to homodyne SFG intensity data is not ideal as the SFG line shape often masks underlying spectral features, resulting in misleading correlation maps. We show that application of correlation analysis to heterodyne SFG experiments restores the qualitative utility of such analyses. An example is provided for the case of leucine adsorption onto surfaces of varying hydrophobicity.
DOI : 10.1016/j.molstruc.2013.10.074
Anahtar Kelimeler : Nonlinear optics, Vibrational spectroscopy, Surface structure, Two-dimensional correlation analysis
ISSN: 0022-2860
Cilt: 1069
Sayfa: 103-111
Sınıflandırma :
19
Charge and reduce: A fixed-parameter algorithm for String-to-String Correction
Dergi Makalesi

Dergi Makalesi
Kaynak :
Science Direct
Dergi:
Discrete Optimization
Yayıncı:
Elsevier
Yazar(lar) :
Faisal N. Abu-Khzam , Henning Fernau , Michael A. Langston , Serena Lee-Cultura , Ulrike Stege
Yıl :
2011
Ulrike Stege
Yayıncı Web Sitesi
Tam Metin
Kaydet Alıntıla
String distance problems typically ask for a minimum number of permitted operations to transform one string into another. Such problems find application in a wide variety of areas, including error-correcting codes, parsing theory, speech recognition, and computational biology, to name a few. Here we consider a classic string distance problem, the NP-complete String-to-String Correction problem, first studied by Wagner some 35 years ago. In this problem, we are asked whether it is possible to transform string x into string y with at most k operations on x, where permitted operations are single-character deletions and adjacent character exchanges. We prove that String-to-String Correction is fixed-parameter tractable, for parameter k, and present a simple fixed-parameter algorithm that solves the problem in O(2kn) time. We also devise a bounded search tree algorithm, and introduce a bookkeeping technique that we call charge and reduce. This leads to an algorithm whose running time is O(1.6181kn).
DOI : 10.1016/j.disopt.2010.10.003
Anahtar Kelimeler : Fixed-parameter algorithm, String-to-String Correction, Charge and reduce
ISSN: 1572-5286
Sayı: 1
Cilt: 8
Sayfa: 41-49
Sınıflandırma :
20
Teaching Quantum Computing to High-School-Aged Youth: A Hands-On Approach
Dergi Makalesi

Dergi Makalesi
Kaynak :
IEEE Xplore
Dergi:
IEEE Transactions on Quantum Engineering
Yayıncı:
Institute of Electrical and Electronics Engineers (IEEE)
Yazar(lar) :
Prashanti Priya Angara , Ulrike Stege , Andrew MacLean , Hausi A. Muller , Tom Markham
Konu :
Components, Circuits, Devices and Systems, Engineered Materials, Dielectrics and Plasmas
Yıl :
2022
Ulrike Stege
Yayıncı Web Sitesi
Tam Metin
Kaydet Alıntıla
Quantum computing is aninterdisciplinary field that lies at the intersection of mathematics, quantum physics, and computer science, and finds applications in areas including optimization, machine learning, and simulation of chemical, physical, and biological systems. It has the potential to help solve problems that so far have no satisfying method solving them, and to provide significant speedup to solutions when compared with their best classical approaches. In turn, quantum computing may allow us to solve problems for inputs that so far are deemed practically intractable. With the computational power of quantum computers and the proliferation of quantum development kits, quantum computing is anticipated to become mainstream, and the demand for a skilled workforce in quantum computing is expected to increase significantly. Therefore, quantum computing education is ramping up. This article describes our experiences in designing and delivering quantum computing workshops for youth (Grades 9–12). We introduce students to the world of quantum computing in innovative ways, such as newly designed unplugged activities for teaching basic quantum computing concepts. We also take a programmatic approach and introduce students to the IBM Quantum Experience using Qiskit and Jupyter notebooks. Our contributions are as follows. First, we present creative ways to teach quantum computing to youth with little or no experience in science, technology, engineering, and mathematics areas; second, we discuss diversity and highlight various pathways into quantum computing from quantum software to quantum hardware; and third, we discuss the design and delivery of online and in-person motivational, introductory, and advanced workshops for youth.
DOI : 10.1109/tqe.2021.3127503
Anahtar Kelimeler : Quantum computing, Quantum mechanics, Conferences, Qubit, Programming profession, Industries, Software, computer aided instruction, computer science education, educational courses, educational institutions, engineering education, physics education, quantum computing, teaching, teaching Quantum computing, quantum computers, quantum computing education, basic quantum computing concepts, Computer science (CS) unplugged (CS Unplugged), education, entanglement, high-school-aged youth, measurement, qiskit, quantum computing, quantum computing games, quantum gates, quantum teleportation, qubit systems, superposition, teachers, training, workforce development
ISSN: 2689-1808
Cilt: 3
Sayfa: 1-15
21
Rotations, Projections, Direction Cosines, and Vibrational Spectra
Dergi Makalesi

Dergi Makalesi
Kaynak :
Taylor and Francis
Dergi:
Applied Spectroscopy Reviews
Yayıncı:
Informa UK Limited
Yazar(lar) :
Sandra Roy , Kuo-Kai Hung , Ulrike Stege , Dennis K. Hore
Konu :
Instrumentation, Spectroscopy
Yıl :
2013
Ulrike Stege
Yayıncı Web Sitesi
Tam Metin
Kaydet Alıntıla
We provide a complete and consistent framework in which vibrational spectra may be modeled from molecular properties and molecular properties may be gleaned from vibrational spectra. This includes practical advice on how to define and use the rotation operators when moving between laboratory and molecular coordinate systems. At the same time, we provide some tips for the facile comparison of analytical orientation distributions and the construction of spectra from molecular dynamics simulations. We illustrate these approaches for infrared absorption, Raman scattering, and vibrational sum-frequency generation spectroscopy.
DOI : 10.1080/05704928.2013.819810
Anahtar Kelimeler : Spectral modeling, molecular structure, IR absorption, Raman scattering, visible-infrared sum-frequency generation
ISSN: 0570-4928
Sayı: 3
Cilt: 49
Sayfa: 233-248
22
A refined search tree technique for Dominating Set on planar graphs
Dergi Makalesi

Dergi Makalesi
Kaynak :
Science Direct
Dergi:
Journal of Computer and System Sciences
Yayıncı:
Elsevier
Yazar(lar) :
Jochen Alber , Hongbing Fan , Michael R. Fellows , Henning Fernau , Rolf Niedermeier , Fran Rosamond , Ulrike Stege
Yıl :
2005
Ulrike Stege
Yayıncı Web Sitesi
Tam Metin
Kaydet Alıntıla
We establish a refined search tree technique for the parameterized DOMINATING SET problem on planar graphs. Here, we are given an undirected graph and we ask for a set of at most k vertices such that every other vertex has at least one neighbor in this set. We describe algorithms with running times O(8kn) and O(8kk+n3), where n is the number of vertices in the graph, based on bounded search trees. We describe a set of polynomial time data-reduction rules for a more general “annotated” problem on black/white graphs that asks for a set of k vertices (black or white) that dominate all the black vertices. An intricate argument based on the Euler formula then establishes an efficient branching strategy for reduced inputs to this problem. In addition, we give a family examples showing that the bound of the branching theorem is optimal with respect to our reduction rules. Our final search tree algorithm is easy to implement; its analysis, however, is involved.
DOI : 10.1016/j.jcss.2004.03.007
Anahtar Kelimeler : NP-complete problem, Dominating set, Planar graph, Fixed-parameter tractability, Exact algorithm, Search tree
ISSN: 0022-0000
Sayı: 4
Cilt: 71
Sayfa: 385-405
Sınıflandırma :
23
LiveTalk: A Framework for Collaborative Browser-Based Replicated-Computation Applications
Konferans Bildirileri

Konferans Bildirileri
Kaynak :
IEEE Xplore
Yazar(lar) :
Matthew Hemmings , Daniel Ingalls , Robert Krahn , Rick McGeer , Glenn Ricart , Marko Roder , Ulrike Stege
Konu :
Communication, Networking and Broadcast Technologies
Yıl :
2016
Ulrike Stege
Yayıncı Web Sitesi
Tam Metin
Kaydet Alıntıla
In this paper we describe LiveTalk, a framework for Collaborative Browser-based Replicated-Computation applications. LiveTalk permits multiple users separated across the wide area to interact with separate copies of a single application, sharing a single virtual workspace, using very little network bandwidth. LiveTalk features an integrated, browser-based programming environment with native graphics and live evaluation, an integrated, pluggable web server, and a simple messaging service that serves to coordinate activity on shared application sessions, and provides for multiple, mutually-isolated sessions. The first use case for LiveTalk are collaborative big-data visualizations running on thin-client devices such as cellular phones, tablets, and netbooks. These applications form part of a new class of application where the distributed Cloud is leveraged to provide low latency, and high-bandwidth access to geographically disparate users while maintaining the feel of immediacy associated with local computation. The primary motivation of this work is to permit low latency, collaborative applications to be built quickly and easily, while requiring no setup for use by the end-user.
DOI : 10.1109/itc-28.2016.144
Anahtar Kelimeler : Cloud computing, Servers, Bandwidth, Programming, Google, Collaboration, Games
24
Connecting a set of circles with minimum sum of radii
Dergi Makalesi

Dergi Makalesi
Kaynak 1:
Science Direct
Kaynak 2:
arXiv
Dergi:
Computational Geometry
Yayıncı:
Elsevier
Yazar(lar) :
Erin W. Chambers , Sándor P. Fekete , Hella-Franziska Hoffmann , Dimitri Marinakis , Joseph S.B. Mitchell , Venkatesh Srinivasan , Ulrike Stege , Sue Whitesides
Yıl :
2018
Ulrike Stege
Tam Metin
Kaydet Alıntıla
We consider the problem of assigning radii to a given set of points in the plane, such that the resulting set of disks is connected, and the sum of radii is minimized. We prove that the problem is NP-hard in planar weighted graphs if there are upper bounds on the radii and sketch a similar proof for planar point sets. For the case when there are no upper bounds on the radii, the complexity is open; we give a polynomial-time approximation scheme. We also give constant-factor approximation guarantees for solutions with a bounded number of disks; these results are supported by lower bounds, which are shown to be tight in some of the cases. Finally, we show that the problem is polynomially solvable if a connectivity tree is given, and we conclude with some experimental results.
DOI : 10.1016/j.comgeo.2017.06.002
Anahtar Kelimeler : Intersection graphs, Connectivity problems, NP-hardness problems, Approximation, Upper and lower bounds
ISSN: 0925-7721
Cilt: 68
Sayfa: 62-76
Sınıflandırma :
25
SPARCS from the University of Victoria: Supporting Sustainable and Integrated Outreach Activities for Educators and Young Minds
Konferans Bildirileri

Konferans Bildirileri
Kaynak :
IEEE Xplore
Yazar(lar) :
Jennifer Murdoch , Anissa Agah St. Pierre , Yvonne Coady , Sarah Carruthers , Celina Gibbs , Steven Lonergan , Gautam Srivastava , Ulrike Stege , Onat Yazir
Konu :
Engineering Profession
Yıl :
2007
Ulrike Stege
Yayıncı Web Sitesi
Tam Metin
Kaydet Alıntıla
Although IT industry is flourishing, student enrolment in Computer Science and related Engineering post-secondary degree programs is low. The causes and issues surrounding this trend are diverse, inter-related, and vastly complex; a consensus may never be reached regarding the nature of these issues affected by both global and local factors. Is a consensus regarding underlying causes and best practices required to create and sustain an infrastructure for effective outreach? Perhaps not. In this article, we discuss five key supportive mechanisms that are critical to sustained and integrated outreach initiatives at the grassroots level. We discuss these mechanisms using the example of SPARCS (Solving Problems with Algorithms, Robots, and Computers), an initiative at the University of Victoria, British Columbia (BC), Canada. We further consider the tradeoffs associated with a vertical/centralized infrastructure versus a horizontal/distributed infrastructure.
DOI : 10.1109/mgdete.2007.4760371
Anahtar Kelimeler : Computer science, Educational institutions, Educational technology, Communications technology, Computer science education, Mathematics, Computer industry, Best practices, North America, Educational programs, computer science education, educational institutions, engineering education, University of Victoria, integrated outreach activities, sustainable activities, IT industry, British Columbia, Canada
Sınıflandırma :
26
Connectivity Graphs of Uncertainty Regions
Dergi Makalesi

Dergi Makalesi
Kaynak :
Springer Link
Dergi:
Algorithmica
Yazar(lar) :
Erin Chambers , Alejandro Erickson , Sándor P. Fekete , Jonathan Lenchner , Jeff Sember , Venkatesh Srinivasan , Ulrike Stege , Svetlana Stolpner , Christophe Weibel , Sue Whitesides
Konu :
Applied Mathematics, Computer Science Applications, General Computer Science
Yıl :
2016
Ulrike Stege
Yayıncı Web Sitesi
Tam Metin
Kaydet Alıntıla
We study connectivity relations among points, where the precise location of each input point lies in a region of uncertainty. We distinguish two fundamental scenarios under which uncertainty arises. In the favorable Best-Case Uncertainty, each input point can be chosen from a given set to yield the best possible objective value. In the unfavorable Worst-Case Uncertainty, the input set has worst possible objective value among all possible point locations, which are uncertain due, for example, to imprecise data. We consider these notions of uncertainty for the bottleneck spanning tree problem, giving rise to the following Best-Case Connectivity with Uncertainty problem: given a family of geometric regions, choose one point per region, such that the longest edge length of an associated geometric spanning tree is minimized. We show that this problem is NP-hard even for very simple scenarios in which the regions are line segments or squares. On the other hand, we give an exact solution for the case in which there are \(n+k\) regions, where k of the regions are line segments and n of the regions are fixed points. We then give approximation algorithms for cases where the regions are either all line segments or all unit discs. We also provide approximation methods for the corresponding Worst-Case Connectivity with Uncertainty problem: Given a set of uncertainty regions, find the minimal distance r such that for any choice of points, one per region, there is a spanning tree among the points with edge length at most r.
DOI : 10.1007/s00453-016-0191-2
Anahtar Kelimeler : Uncertainty, Geometric optimization, Connectivity, Worst-case connectivity, Best-case connectivity
ISSN: 0178-4617 1432-0541
Sayı: 3
Cilt: 78
Sayfa: 990-1019
Sınıflandırma :
27
The Ignite Distributed Collaborative Scientific Visualization System
Konferans Bildirileri

Konferans Bildirileri
Kaynak :
IEEE Xplore
Yazar(lar) :
Sushil Bhojwani , Matthew Hemmings , Daniel Ingalls , Jens Lincke , Robert Krahn , David Lary , Patrick McGeer , Glenn Ricart , Marko Roeder , Yvonne Coady , Ulrike Stege
Konu :
Communication, Networking and Broadcast Technologies, Computing and Processing
Yıl :
2015
Ulrike Stege
Yayıncı Web Sitesi
Tam Metin
Kaydet Alıntıla
We describe the Ignite Distributed Collaborative Scientific Visualization System (IDCVS), a system which permits real-time interaction and visual collaboration around large data sets, with an initial emphasis on scientific data. The IDCVS offers such a collaborative environment, with real-time interaction on any device between users separated across the wide area. It provides seamless interaction and immediate updates even under heavy load and when users are widely separated: the design goal was to fetch a data set consisting of 30,000 points from a server and render it within 150ms, for a user anywhere in the world, and reflect changes made by a user in one location to all other users within a bound provided by network latency. The system was demonstrated successfully on a significant worldwide air pollution data set, with values on 10, 25, 50, and 100km worldwide grids, monthly over an 18-year period. It was demonstrated on a wide variety of clients, including laptop, tablet, and smartphone.
DOI : 10.1109/cloudcom.2015.65
Anahtar Kelimeler : Servers, Collaboration, Data visualization, Computer architecture, Games, Browsers, Continents, data visualisation, groupware, interactive systems, laptop computers, mobile computing, natural sciences computing, rendering (computer graphics), smart phones, Ignite Distributed Collaborative Scientific Visualization System, IDCVS, real-time interaction, visual collaboration, scientific data, collaborative environment, seamless interaction, immediate update, rendering, network latency, air pollution data set, laptop, tablet, smartphone, Visualization, Distributed Cloud

Yayın Yılı

Sınırla

Doküman Türü
Tümü

Veri Tabanı
Tümü

Dergi İsmi
Tümü

Disiplin
Tümü

Disipline Göre İlgililik

Alt Disiplin
Tümü

Konu
Tümü

Yayıncı
Tümü

Lisan
Tümü

X
Filtreler