In John Tantalo's on-line game Planarity the player is given a non-plane straight-line drawing of a planar graph. the aim is to make the drawing plane as quickly as possible by moving vertices. Pach and Tardos hav...
详细信息
ISBN:
(数字)9783540775669
ISBN:
(纸本)9783540775652
In John Tantalo's on-line game Planarity the player is given a non-plane straight-line drawing of a planar graph. the aim is to make the drawing plane as quickly as possible by moving vertices. Pach and Tardos have posed a related problem: can any straight-line drawing of any planar graph with n vertices be made plane by vertex moves while keeping Omega(n(epsilon)) vertices fixed for some absolute constant epsilon > 0? It is known that three vertices can always be kept (if n > 5). We still do not solve the problem of Pach and Tardos, but we report some progress. We prove that the number of vertices that can be kept actually grows withthe size of the graph. More specifically, we give a lower bound of Omega(root log n/ log log n) on this number. By the same technique we show that in the case of outerplanar graphs we can keep a lot more, namely Omega(root n) vertices. We also construct a family of outerplanar graphs for which this bound is asymptotically tight.
We consider computations of a Turing machine under noise that causes consecutive violations of the machine's transition function. Given a constant upper bound β on the size of bursts of faults, we construct a Tur...
详细信息
Usability is a quality characteristic of a software product or system. User-centered design (UCD) is an approach focusing on making systems usable. However, improving the position of UCD is widely recognized as a chal...
详细信息
Hawkes processes have been shown to be efficient in modeling bursty sequences in a variety of applications, such as finance and social network activity analysis. Traditionally, these models parameterize each process i...
详细信息
ISBN:
(纸本)9781577358664
Hawkes processes have been shown to be efficient in modeling bursty sequences in a variety of applications, such as finance and social network activity analysis. Traditionally, these models parameterize each process independently and assume that the history of each point process can be fully observed. Such models could however be inefficient or even prohibited in certain real-world applications, such as in the field of education, where such assumptions are violated. Motivated by the problem of detecting and predicting student procrastination in students Massive Open Online Courses (MOOCs) with missing and partially observed data, in this work, we propose a novel personalized Hawkes process model (RCHawkes-Gamma) that discovers meaningful student behavior clusters by jointly learning all partially observed processes simultaneously, without relying on auxiliary features. Our experiments on both synthetic and real-world education datasets show that RCHawkes-Gamma can effectively recover student clusters and their temporal procrastination dynamics, resulting in better predictive performance of future student activities. Our further analyses of the learned parameters and their association with student delays show that the discovered student clusters unveil meaningful representations of various procrastination behaviors in students.
Information systems have to work correctly and securely as expected (dependability);have to be able to communicate and understand each other's data (interoperability);and have to be able to change in an evolutiona...
详细信息
Information systems have to work correctly and securely as expected (dependability);have to be able to communicate and understand each other's data (interoperability);and have to be able to change in an evolutionary way similarly to how the organizations and their business processes are changing (evolutionary). To write software we must know the requirements;to prescribe the requirements we have to understand the domain;to understand the domain we have to analyze and model one. the domain or application domain (e.g. banking, healthcare, clinical laboratory and etc.) can be anything to which computing can be applied. In analyzing and modeling domains we use archetypes and archetype patterns as meta-models. We explain what the archetypes and archetype patterns are and how we utilize them in the development of domain models, requirements, and software in order to meet the dependability, interoperability and evolutionary criteria. Crown Copyright (C) 2014 Published by Elsevier B. V. this is an open access article under the CC BY-NC-ND license.
SOFSEM 2001, the International conference on currenttrends in theory and practice of Informatics, was held on November 24 – December 1, 2001 in the ? well-known spa Pie?stany, Slovak Republic. this was the 28th annu...
详细信息
ISBN:
(数字)9783540456278
ISBN:
(纸本)9783540429128
SOFSEM 2001, the International conference on currenttrends in theory and practice of Informatics, was held on November 24 – December 1, 2001 in the ? well-known spa Pie?stany, Slovak Republic. this was the 28th annual conference in the SOFSEM series organized either in the Slovak or the Czech Republic. SOFSEM has a well-established tradition. currently it is a broad, multid- ciplinary conference, devoted to the theory and practice of software systems. Its aim is to foster cooperation among professionals from academia and industry working in various areas of informatics. the scienti?c program of SOFSEM consists of invited talks, which determine the topics of the conference, and short contributed talks presenting original - sults. the topics of the invited talks are chosen so as to cover the whole range from theory to practice and to bring interesting research areas to the attention of conference participants. For the year 2001, the following three directions were chosen for presentation by the SOFSEM Steering Committee: – trends in Informatics – Enabling Technologies for Global Computing – Practical Systems Engineering and Applications the above directions were covered through 12 invited talks presented by pro- nent researchers. there were 18 contributed talks, selected by the international Program Committee from among 46 submitted papers. the conference was also accompanied by workshops on Electronic Commerce Systems (coordinated by H. D. Zimmermann) and Soft Computing (coordinated by P. H´ajek).
Model complexity of feedforward neural networks is studied in terms of rates of variable-basis approximation. Sets of functions, for which the errors in approximation by neural networks with n hidden units converge to...
详细信息
A graph with forbidden transitions is a pair (G, F-G) where G := (V-G, E-G) is a graph and FG is a subset of the set {({y, x}, {x, z}) epsilon E-G(2)}. A path in a graph with forbidden transitions (G, F-G) is a path i...
详细信息
ISBN:
(纸本)9783642358432
A graph with forbidden transitions is a pair (G, F-G) where G := (V-G, E-G) is a graph and FG is a subset of the set {({y, x}, {x, z}) epsilon E-G(2)}. A path in a graph with forbidden transitions (G, F-G) is a path in G such that each pair ({y, x}, {x, z}) of consecutive edges does not belong to FG. It is shown in [S. Szeider, Finding paths in graphs avoiding forbidden transitions, DAM 126] that the problem of deciding the existence of a path between two vertices in a graph with forbidden transitions is Np-complete. We give an exact exponential time algorithm that decides in time O(2(n) center dot n(5) center dot log(n)) whether there exists a path between two vertices of a given n-vertex graph with forbidden transitions. We also investigate a natural extension of the minimum cut problem: we give a polynomial time algorithm that computes a set of forbidden transitions of minimum size that disconnects two given vertices (while in a minimum cut problem we are seeking for a minimum number of edges that disconnect the two vertices). the polynomial time algorithm for that second problem is obtained via a reduction to a standard minimum cut problem in an associated allowed line graph.
the mathematical analysis of robustness and error-tolerance of complex networks has been in the center of research interest. On the other hand, little work has been done when the attack-tolerance of the vertices or ed...
详细信息
ISBN:
(纸本)9783030108014;9783030108007
the mathematical analysis of robustness and error-tolerance of complex networks has been in the center of research interest. On the other hand, little work has been done when the attack-tolerance of the vertices or edges are not independent but certain classes of vertices or edges share a mutual vulnerability. In this study, we consider a graph and we assign colors to the vertices or edges, where the color-classes correspond to the shared vulnerabilities. An important problem is to find robustly connected vertex sets: nodes that remain connected to each other by paths providing any type of error (i.e. erasing any vertices or edges of the given color). this is also known as color-avoiding percolation. In this paper, we study various possible modeling approaches of shared vulnerabilities, we analyze the computational complexity of finding the robustly (color-avoiding) connected components. We find that the presented approaches differ significantly regarding their complexity.
this book contains the invited and contributed papers selected for presentation at SOFSEM 2021, the 47th International conference on currenttrends in theory and practice of computerscience, which was held online dur...
详细信息
ISBN:
(数字)9783030677312
ISBN:
(纸本)9783030677305
this book contains the invited and contributed papers selected for presentation at SOFSEM 2021, the 47th International conference on currenttrends in theory and practice of computerscience, which was held online during January 25–28, 2021, hosted by the Free University of Bozen-Bolzano, Italy.
暂无评论