### ?

## Algorithms and Data Structures. WADS 2019. Lecture Notes in Computer Science

Vol. 11646.
Springer, 2019.

16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5–7, 2019, Proceedings

Beisegel J., Chudnovsky M., Gurvich V. et al., , in : Algorithms and Data Structures. WADS 2019. Lecture Notes in Computer Science. Vol. 11646.: Springer, 2019. P. 126-139.

A vertex v in a graph G is said to be avoidable if every induced two-edge path with midpoint v is contained in an induced cycle. Generalizing Dirac’s theorem on the existence of simplicial vertices in chordal graphs, Ohtsuki et al. proved in 1976 that every graph has an avoidable vertex. In a different generalization, Chvátal et al. gave in 2002 a characterization of graphs ...

Added: October 26, 2021

Language:
English

Vildhoj H. W., Starikovskaya T., , in : Lecture Notes in Computer Science. Vol. 7922: Proceedings of the 24th Symposium on Combinatorial Pattern Matching.: Berlin : Springer, 2013. P. 223-234.

Lexicographically minimal and lexicographically maximal suffixes of a string are fundamental notions of stringology. It is well known that the lexicographically minimal and maximal suffixes of a given string $S$ can be computed in linear time and space by constructing a suffix tree or a suffix array of $S$. Here we consider the case when ...

Added: October 30, 2013

Babenko M. A., Gawrychowski P., Kociumaka T. et al., , in : Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. : San Diego : SIAM, 2015. P. 572-591.

We present an improved wavelet tree construction algorithm and discuss its applications to a number of rank/select problems for integer keys and strings. Given a string of length n over an alphabet of size ω ≤ n, our method builds the wavelet tree in O(n log ω √log n) time, improving upon the state-of-the-art algorithm ...

Added: October 4, 2014

Babenko M., Kolesnichenko I., Starikovskaya T., , in : Lecture Notes in Computer Science. Vol. 7922: Proceedings of the 24th Symposium on Combinatorial Pattern Matching.: Berlin : Springer, 2013. P. 28-37.

Lexicographically minimal and lexicographically maximal suffixes of a string are fundamental notions of stringology. It is well known that the lexicographically minimal and maximal suffixes of a given string S can be computed in linear time and space by constructing a suffix tree or a suffix array of S. Here we consider the case when ...

Added: October 30, 2013

Kucherov G., Nekrich Y., Starikovskaya T., , in : Lecture Notes in Computer Science. Vol. 7608: Proceedings of the 19th International Symposium on String Processing and Information Retrieval.: Berlin : Springer, 2012. P. 307-317.

We study the following three problems of computing generic or discriminating words for a given collection of documents. Given a pattern $P$ and a threshold $d$, we want to report (i) all longest extensions of $P$ which occur in at least $d$ documents, (ii) all shortest extensions of $P$ which occur in less than $d$ ...

Added: October 30, 2013

Vildhoj H. W., Starikovskaya T., , in : Combinatorial Algorithms. 25th International Workshop, IWOCA 2014, Duluth, MN, USA, October 15-17, 2014, Revised Selected Papers. Vol. 8986.: Springer, 2014. P. 338-350.

In this paper we study the structure of suffix trees. Given an unlabelled tree $\tau$ on $n$ nodes and suffix links of its internal nodes, we ask the question "Is $\tau$ a suffix tree?", i.e., is there a string $S$ whose suffix tree has the same topological structure as $\tau$? We place no restrictions on ...

Added: October 4, 2014

Maxim Babenko, Gawrychowski P., Kociumaka T. et al., Theoretical Computer Science 2016 Vol. 638 P. 112-121

We consider the problems of computing the maximal and the minimal non-empty suffixes of substrings of a longer text of length . n. For the minimal suffix problem we show that for every . τ, . 1≤τ≤logn, there exists a linear-space data structure with . O(τ) query time and . O(nlogn/τ) preprocessing time. As a ...

Added: October 8, 2015

Berlin, Heidelberg : Springer, 2013

This volume contains the papers presented at the 6th International Conference on Similarity Search and Applications (SISAP 2013), held at A Coruna, Spain, during October 2–4, 2013. The International Conference on Similarity Search and Applications (SISAP) is an annual forum for researchers and application developers in the area of similarity data management. It aims at the technological problems shared ...

Added: September 27, 2013

Konstantin Bazhanov, Obiedkov S., Annals of Mathematics and Artificial Intelligence 2014 Vol. 70 No. 1-2 P. 5-24

In this paper, we consider algorithms involved in the computation of the Duquenne–Guigues basis of implications. The most widely used algorithm for constructing the basis is Ganter’s Next Closure, designed for generating closed sets of an arbitrary closure system. We show that, for the purpose of generating the basis, the algorithm can be optimized. We ...

Added: October 26, 2013

Kucherov G., Nekrich Y., Gawrychowski P. et al., , in : Lecture Notes in Computer Science. Vol. 8214: Proceedings of the 20th Symposium on String Processing and Information Retrieval.: Berlin : Springer, 2013. P. 129-140.

We revisit two variants of the problem of computing minimal discriminating words studied in [5]. Given a pattern P and a threshold d, we want to report (i) all shortest extensions of P which occur in less than d documents, and (ii) all shortest extensions of P which occur only in d selected documents. For ...

Added: October 30, 2013

МГУ, МАКС Пресс, 2018

The proceedings of the tenth international conference "Discrete Models in Control Systems Theory" (Moscow and Moscow Region, May 23-25, 2018) includes 100 papers on such topics as discrete functional systems, properties of discrete functions, synthesis and complexity of control systems, reliability, control and diagnostics of control systems, automata, graph theory, combinatorics, coding theory, mathematical methods ...

Added: June 14, 2018

Springer, 2020

This special issue of Theory of Computing Systems consists of extended journal papers originally presented at the 13th International Computer Science Symposium in Russia (CSR 2018) held on June 6–10, 2018 in Moscow, Russia. The event was hosted by National Research University Higher School of Economics and chaired by Vladimir V. Podolskii. Preliminary versions of ...

Added: October 27, 2020

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2019

Added: November 13, 2019

NY : Springer, 2013

Information systems have been developed in parallel with computer science, although information systems have roots in different disciplines including mathematics, engineering, and cybernetics. Research in information systems is by nature very interdisciplinary. As it is evidenced by the chapters in this book, dynamics of information systems has several diverse applications. The book presents the state-of-the-art ...

Added: December 12, 2013

Babkina T. S., Demidovskij A., Babkin E., International Journal of Big Data Intelligence 2018 Vol. 5 No. 3 P. 143-155

This paper presents two new approaches to solving a classical NP-hard problem of maximum clique problem (MCP), which frequently arises in the domain of information management, including design of database structures and big data processing. In our research, we are focusing on solving that problem using the paradigm of artificial neural networks. The first approach ...

Added: October 3, 2018

Switzerland : Springer, 2017

This book constitutes the refereed proceedings of the Third Russian Supercomputing Days, RuSCDays 2017, held in Moscow, Russia, in September 2017. The 41 revised full papers and one revised short paper presented were carefully reviewed and selected from 120 submissions. The papers are organized in topical sections on parallel algorithms; supercomputer simulation; high performance architectures, ...

Added: November 15, 2017

Delong A., Osokin A., Isack H. et al., , in : Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2010). : San Francisco : IEEE, 2010. P. 2173-2180.

The α-expansion algorithm [4] has had a significant impact in computer vision due to its generality, effectiveness, and speed. Thus far it can only minimize energies that involve unary, pairwise, and specialized higher-order terms. Our main contribution is to extend α-expansion so that it can simultaneously optimize “label costs” as well. An energy with label ...

Added: October 18, 2017

Berlin : Springer, 2012

This book constitutes the refereed proceedings of the 23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012, held in Helsinki, Finalnd, in July 2012.
The 33 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 60 submissions. The papers address issues of searching and matching strings and more complicated patterns ...

Added: October 30, 2013

M. Polyakova, Semenov A. V., Kovalyuk V. et al., IEEE Transactions on Applied Superconductivity 2019 Vol. 29 No. 5 P. 1-5

We present a simple quantum detector tomography
protocol, which allows, without ambiguities, to measure the twospot
detection efficiency and extract the hot-spot interaction length
of SNSPDs with unity intrinsic detection efficiency. We identify a
significant parasitic contribution to the measured two-spot efficiency,
related to an effect of the bias circuit, and find a way to rule
out this contribution during data ...

Added: October 23, 2019

Соколов Б. В., Ivanov D., Dolgui A., Algorithms 2018 Vol. 11 No. 5 P. 57

Added: February 11, 2020

Bliznets Ivan, Cygan M., Komosa P. et al., , in : Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. : SIAM, 2016. P. 1132-1151.

In this work, we focus on several completion problems for subclasses of chordal graphs: Minimum Fill-In, Interval Completion, Proper IntervalCompletion, Threshold Completion, and Trivially Perfect Completion. In these problems, the task is to add at most k edges to a given graph in order to obtain a chordal, interval, proper interval, threshold, or trivially perfect graph, respectively. We prove the following lower bounds ...

Added: October 31, 2018

Voskov L., Efremov S. G., В кн. : Distributed computer and communication networks: control, computation, communications (DCCN-2013). : М. : Техносфера, 2013. С. 197-199.

In this paper we propose models and algorithms for increasing lifetime of dynamically reconfigurable wireless sensor networks with a mobile sink and anonymous power supplies. A new definition and assessment model of a network lifetime in case of dynamic reconfiguration are given. We propose a new method for dynamic reconfiguration aimed at finding an optimal ...

Added: February 12, 2014

Edward Elgar Publishing, 2019

The digital economy is gradually gaining traction through a variety of recent technological developments, including the introduction of the Internet of things, artificial intelligence and markets for data. This innovative book contains contributions from leading competition law scholars who map out and investigate the anti-competitive effects that are developing in the digital economy. ...

Added: August 4, 2020

Babenko M. A., Goldberg A. V., Gupta A. ,. et al., ACM Transactions on Algorithms 2016 Vol. 13 No. 1 P. 16:1-16:17

We consider the hub label optimization problem, which arises in designing fast preprocessing-based shortest- path algorithms. We give O(log n)-approximation algorithms for the objectives of minimizing the maximum label size (l∞-norm) and simultaneously minimizing a constant number of lp-norms. Prior to this, an O(log n)- approximation algorithm was known [Cohen et al. 2003] only for ...

Added: January 12, 2017