New Results on Weighted Independent Domination

Loozin V. V.; D. Malyshev; Mosca R.; V. A. Zamaraev

doi:10.1007/978-3-319-68705-6_30

АБВ
АБВ
АБВ

Обычная версия сайта

Priority areas

by year

Subject

News

October 1, 2026

HSE Researchers Show How Congenital Motor Disorders Affect Brain Development

Researchers from HSE University’s Institute for Cognitive Neuroscience have synthesised the findings of their previous studies on brain development in children with obstetric brachial plexus palsy and arthrogryposis. Their analysis shows that impaired motor function in early childhood not only limits children’s motor experience but also affects memory, categorical thinking, and information processing. The study has been published in Frontiers in Psychology.

October 1, 2026

Window into the Body: Scientists Develop Neural Network to Detect Risk of 15 Diseases from Retinal Images

Russian universities, with the participation of HSE University, Sber, and Z-union, have developed a neural network that can simultaneously assess the risk of 15 types of pathology from retinal photographs, including not only eye diseases but also cardiovascular conditions. The AI system can help clinicians detect potentially concerning changes at an early stage, identify signs reflecting the condition of retinal blood vessels, and determine whether a patient may need further examination. The paper has been published in Frontiers in Medicine.

September 30, 2026

'We Did Not Limit the Time for Questions'

The International Laboratory for Supercomputer Atomistic Modelling and Multi-Scale Analysis at HSE University held a major conference on molecular dynamics. Participants had the opportunity to attend all the presentations, while speakers were given as much time as they needed to answer questions. The HSE News Service interviewed Grigory Smirnov, Head of the Laboratory, and Genri Norman, Chief Research Fellow, about the conference preparations and the discussions it generated.

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications

?

New Results on Weighted Independent Domination

P. 399–411.

Loozin V. V., Malyshev D., Mosca R., Zamaraev V. A.

Weighted independent domination is an NP-hard graph problem, which remains computationally intractable in many restricted graph classes. Only few examples of classes are available, where the problem admits polynomial-time solutions. In the present paper, we extend the short list of such classes with two new examples.

Language: English

Full text

DOI

Keywords: independent domination computation complexity

In book

Graph-Theoretic Concepts in Computer Science, 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers

Vol. 10520. , Springer, 2017.

Semitractability of optimal stopping problems via a weighted stochastic mesh algorithm

Belomestny D., Kaledin M., Schoenmakers J., Mathematical Finance 2020 Vol. 30 No. 4 P. 1591–1616

In this paper, we propose a Weighted Stochastic Mesh (WSM) algorithm for approximating the value of discrete- and continuous-time optimal stopping problems. In this context, we consider tractability of such problems via a useful notion of semitractability and the introduction of a tractability index for a particular numerical solution algorithm. It is shown that in ...

Added: May 8, 2020

Independent domination versus weighted independent domination

Lozin V. V., Malyshev D., Mosca R. et al., Information Processing Letters 2020 Vol. 156 P. 105914

Independent domination is one of the rare problems for which the complexity of weighted and unweighted versions is known to be different in some classes of graphs. Trying to better understand the gap between the two versions of the problem, in the present paper we prove two complexity results. First, we extend NP-hardness of the weighted ...

Added: January 16, 2020