检索结果-内蒙古大学图书馆

Polynomial kernels for edge modification problems towards block and strictly chordal graphs

Discrete Mathematics and Theoretical Computer Science 2025年 272卷

作者： Dumas, Maël Perez, Anthony Rocton, Mathis Todinca, Ioan Institute of Informatics University of Warsaw Warsaw Poland Université d’Orléans INSA CVL LIFO UR 4022 Orléans France Algorithms and Complexity Group TU Wien Vienna Austria

We consider edge modification problems towards block and strictly chordal graphs, where one is given an undirected graph G = (V, E) and an integer k ∈ N and seeks to edit (add or delete) at most k edges from G to obtain a block graph or a strictly chordal graph. The completion and deletion variants of these problems are defined similarly by only allowing edge additions for the former and only edge deletions for the latter. Block graphs are a well-studied class of graphs and admit several characterizations, e.g. they are diamond-free chordal graphs. Strictly chordal graphs, also referred to as block duplicate graphs, are a natural generalization of block graphs where one can add true twins of cut-vertices. Strictly chordal graphs are exactly dart and gem-free chordal graphs. We prove the NP-completeness for most variants of these problems and provide: © 2025 by the author(s)

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

A Relative Value Function Based Learning Beam Search for the Longest Common Subsequence Problem 18th

A Relative Value Function Based Learning Beam Search for th...

引用

18th International Conference on Computer Aided Systems Theory, EUROCAST 2022

作者： Huber, M. Raidl, G.R. Algorithms and Complexity Group Institute of Logic and Computation TU Wien Vienna Austria

ISBN: (纸本)9783031253119

Beam search (BS) is a well-known graph search algorithm frequently used to heuristically find good or near-optimal solutions to combinatorial optimization problems. Its most crucial component is a heuristic function that estimates the best achievable length-to-go from any state to a goal state. This function usually needs to be developed specificially for a problem at hand, which is a manual and time-consuming process. Building on previous work, we propose a Relative Value Function Based Learning Beam Search (RV-LBS) to automate this task at least partially by using a multilayer perceptron (MLP) as heuristic function, which is trained in a reinforcement learning manner on many randomly created problem instances. This MLP predicts the difference of the expected solution length from a given state to the expected average solution length of all states at a current BS level. To support the training of the MLP on the longest common subsequence (LCS) problem, a compact fixed-size encoding of the distribution of differences of remaining string lengths to the average string length at the current level is presented. Tests show that a MLP trained by RV-LBS on randomly created small-size problem instances is able to guide BS well also on larger established LCS benchmark instances. The obtained results are highly competitive to the state-of-the-art. © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.

关键词： Benchmarking

来源：评论

学校读者我要写书评

暂无评论

On the fine-grained parameterized complexity of partial scheduling to minimize the makespan 15

On the fine-grained parameterized complexity of partial sche...

引用

15th International Symposium on Parameterized and Exact Computation, IPEC 2020

作者： Nederlof, Jesper Swennenhuis, Céline M.F. Utrecht University Algorithms and Complexity Group Netherlands Eindhoven University of Technology Combinatorial Optimization Group Netherlands

ISBN: (纸本)9783959771726

We study a natural variant of scheduling that we call partial scheduling: In this variant an instance of a scheduling problem along with an integer k is given and one seeks an optimal schedule where not all, but only k jobs, have to be processed. Specifically, we aim to determine the fine-grained parameterized complexity of partial scheduling problems parameterized by k for all variants of scheduling problems that minimize the makespan and involve unit/arbitrary processing times, identical/unrelated parallel machines, release/due dates, and precedence constraints. That is, we investigate whether algorithms with runtimes of the type f(k)nO(1) or nO(f(k)) exist for a function f that is as small as possible. Our contribution is two-fold: First, we categorize each variant to be either in P, NP-complete and fixed-parameter tractable by k, or W[1]-hard parameterized by k. Second, for many interesting cases we further investigate the run time on a finer scale and obtain run times that are (almost) optimal assuming the Exponential Time Hypothesis. As one of our main technical contributions, we give an O(8kk(|V | + |E|)) time algorithm to solve instances of partial scheduling problems minimizing the makespan with unit length jobs, precedence constraints and release dates, where G = (V, E) is the graph with precedence constraints. © Jesper Nederlof and Céline M. F. Swennenhuis

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

Constrained Boundary Labeling 35

Constrained Boundary Labeling

引用

35th International Symposium on algorithms and Computation, ISAAC 2024

作者： Depian, Thomas Nöllenburg, Martin Terziadis, Soeren Wallinger, Markus Algorithms and Complexity Group TU Wien Austria Algorithms cluster TU Eindhoven Netherlands Technical University of Munich Germany

ISBN: (纸本)9783959773546

Boundary labeling is a technique in computational geometry used to label dense sets of feature points in an illustration. It involves placing labels along an axis-aligned bounding box and connecting each label with its corresponding feature point using non-crossing leader lines. Although boundary labeling is well-studied, semantic constraints on the labels have not been investigated thoroughly. In this paper, we introduce grouping and ordering constraints in boundary labeling: grouping constraints enforce that all labels in a group are placed consecutively on the boundary, and ordering constraints enforce a partial order over the labels. We show that it is NP-hard to find a labeling for arbitrarily sized labels with unrestricted positions along one side of the boundary. However, we obtain polynomial-time algorithms if we restrict this problem either to uniform-height labels or to a finite set of candidate positions. Finally, we show that finding a labeling on two opposite sides of the boundary is NP-complete, even for uniform-height labels and finite label positions. © Thomas Depian, Martin Nöllenburg, Soeren Terziadis, and Markus Wallinger.

关键词： Computational geometry

来源：评论

学校读者我要写书评

暂无评论

FPT Approximation for Fair Minimum-Load Clustering 17

FPT Approximation for Fair Minimum-Load Clustering

引用

17th International Symposium on Parameterized and Exact Computation, IPEC 2022

作者： Bandyapadhyay, Sayan Fomin, Fedor V. Golovach, Petr A. Purohit, Nidhi Simonov, Kirill Department of Informatics University of Bergen Norway Algorithms and Complexity Group TU Wien Austria

ISBN: (纸本)9783959772600

In this paper, we consider the Minimum-Load k-Clustering/Facility Location (MLkC) problem where we are given a set P of n points in a metric space that we have to cluster and an integer k > 0 that denotes the number of clusters. Additionally, we are given a set F of cluster centers in the same metric space. The goal is to select a set C ⊆ F of k centers and assign each point in P to a center in C, such that the maximum load over all centers is minimized. Here the load of a center is the sum of the distances between it and the points assigned to it. Although clustering/facility location problems have rich literature, the minimum-load objective has not been studied substantially, and hence MLkC has remained a poorly understood problem. More interestingly, the problem is notoriously hard even in some special cases including the one in line metrics as shown by Ahmadian et al. [APPROX 2014, ACM Trans. algorithms 2018]. They also show APX-hardness of the problem in the plane. On the other hand, the best-known approximation factor for MLkC is O(k), even in the plane. In this work, we study a fair version of MLkC inspired by the work of Chierichetti et al. [NeurIPS, 2017]. Here the input points are partitioned into protected groups, and only clusters that proportionally represent each group are allowed. MLkC is the special case with = 1. For the fair version, we are able to obtain a randomized 3-approximation algorithm in f(k, ) · nO(1) time. Also, our scheme leads to an improved (1 + ϵ)-approximation in the case of Euclidean norm with the same running time (depending also linearly on the dimension d). Our results imply the same approximations for MLkC with running time f(k) · nO(1), achieving the first constant-factor FPT approximations for this problem in general and Euclidean metric spaces. © Sayan Bandyapadhyay, Fedor V. Fomin, Petr A. Golovach, Nidhi Purohit, and Kirill Simonov.

关键词： Topology

来源：评论

学校读者我要写书评

暂无评论

Self-organized transport in noisy dynamic networks

引用

Physical Review E 2024年第4期110卷 044310页

作者： Frederic Folz Kurt Mehlhorn Giovanna Morigi Theoretische Physik Algorithms and Complexity Group

We present a numerical study of multicommodity transport in a noisy, nonlinear network. The nonlinearity determines the dynamics of the edge capacities, which can be amplified or suppressed depending on the local current flowing across an edge. We consider network self-organization for three different nonlinear functions: For all three we identify parameter regimes where noise leads to self-organization into more robust topologies, that are not found by the sole noiseless dynamics. Moreover, the interplay between noise and specific functional behavior of the nonlinearity gives rise to different features, such as (i) continuous or discontinuous responses to the demand strength and (ii) either single or multistable solutions. Our study shows the crucial role of the activation function on noise-assisted phenomena.

关键词： Dynamics of networks Biological networks Stochastic dynamical systems Stochastic networks

来源：评论

学校读者我要写书评

暂无评论

Weighted Model Counting with Twin-Width 25

Weighted Model Counting with Twin-Width

引用

25th International Conference on Theory and Applications of Satisfiability Testing, SAT 2022

作者： Ganian, Robert Pokrývka, Filip Schidler, André Simonov, Kirill Szeider, Stefan Algorithms and Complexity Group TU Wien Austria Masaryk University Brno Czech Republic

ISBN: (纸本)9783959772426

Bonnet et al. (FOCS 2020) introduced the graph invariant twin-width and showed that many NP-hard problems are tractable for graphs of bounded twin-width, generalizing similar results for other width measures, including treewidth and clique-width. In this paper, we investigate the use of twin-width for solving the propositional satisfiability problem (SAT) and propositional model counting. We particularly focus on Bounded-ones Weighted Model Counting (BWMC), which takes as input a CNF formula F along with a bound k and asks for the weighted sum of all models with at most k positive literals. BWMC generalizes not only SAT but also (weighted) model counting. We develop the notion of "signed" twin-width of CNF formulas and establish that BWMC is fixed-parameter tractable when parameterized by the certified signed twin-width of F plus k. We show that this result is tight: it is neither possible to drop the bound k nor use the vanilla twin-width instead if one wishes to retain fixed-parameter tractability, even for the easier problem SAT. Our theoretical results are complemented with an empirical evaluation and comparison of signed twin-width on various classes of CNF formulas. © Robert Ganian, Filip Pokrývka, André Schidler, Kirill Simonov, and Stefan Szeider.

关键词： Computational complexity

来源：评论

学校读者我要写书评

暂无评论

GdMetriX - A NetworkX Extension For Graph Drawing Metrics 32

GdMetriX - A NetworkX Extension For Graph Drawing Metrics

引用

32nd International Symposium on Graph Drawing and Network Visualization, GD 2024

作者： Nöllenburg, Martin Röder, Sebastian Wallinger, Markus Algorithms and Complexity Group TU Wien Austria TU Wien Austria Chair for Efficient Algorithms Technical University of Munich Germany

ISBN: (纸本)9783959773430

networkX is a well-established Python library for network analysis. With gdMetriX, we aim to extend the functionality of networkX and provide common quality metrics used in the field of graph drawing, such as the number of crossings or the angular resolution. In addition, the package provides easy-to-use access to the graph datasets provided by the 'Graph Layout Benchmark Datasets' project from the Northeastern University Visualization Lab. © Martin Nöllenburg, Sebastian Röder, and Markus Wallinger.

关键词： Data visualization

来源：评论

学校读者我要写书评

暂无评论

Parameterized complexity of Feature Selection for Categorical Data Clustering 46

Parameterized Complexity of Feature Selection for Categorica...

引用

46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021

作者： Bandyapadhyay, Sayan Fomin, Fedor V. Golovach, Petr A. Simonov, Kirill Department of Informatics University of Bergen Norway Algorithms and Complexity Group TU Wien Austria

ISBN: (纸本)9783959772013

We develop new algorithmic methods with provable guarantees for feature selection in regard to categorical data clustering. While feature selection is one of the most common approaches to reduce dimensionality in practice, most of the known feature selection methods are heuristics. We study the following mathematical model. We assume that there are some inadvertent (or undesirable) features of the input data that unnecessarily increase the cost of clustering. Consequently, we want to select a subset of the original features from the data such that there is a small-cost clustering on the selected features. More precisely, for given integers (the number of irrelevant features) and k (the number of clusters), budget B, and a set of n categorical data points (represented by m-dimensional vectors whose elements belong to a finite set of values Σ), we want to select m relevant features such that the cost of any optimal k-clustering on these features does not exceed B. Here the cost of a cluster is the sum of Hamming distances (0-distances) between the selected features of the elements of the cluster and its center. The clustering cost is the total sum of the costs of the clusters. We use the framework of parameterized complexity to identify how the complexity of the problem depends on parameters k, B, and |Σ|. Our main result is an algorithm that solves the Feature Selection problem in time f(k,B, |Σ|) mg(k,|Σ|) n2 for some functions f and g. In other words, the problem is fixed-parameter tractable parameterized by B when |Σ| and k are constants. Our algorithm for Feature Selection is based on a solution to a more general problem, Constrained Clustering with Outliers. In this problem, we want to delete a certain number of outliers such that the remaining points could be clustered around centers satisfying specific constraints. One interesting fact about Constrained Clustering with Outliers is that besides Feature Selection, it encompasses many other fundamental problems r

关键词： Budget control

来源：评论

学校读者我要写书评

暂无评论

The Evolution and Implications of the Inosine tRNA Modification

引用

Journal of Molecular Biology 2025年 169187页

作者： Peter T.S. van der Gulik Wouter D. Hoff Algorithms and Complexity Group Centrum Wiskunde & Informatica P.O. Box 94079 1090 GB Amsterdam the Netherlands Department of Microbiology and Molecular Genetics Oklahoma State University Stillwater OK 74078 USA

Ever since the legendary publication by Francis Crick in JMB introducing the wobble hypothesis in 1966, inosine has been a permanent part of molecular biology. This review aims to integrate the rich array of novel insights emerging from subsequent research on the adenine-to-inosine modification of tRNA, with an emphasis on the results obtained during the last 5 years. Both the grand panorama of 4 billion years of evolution of life and the medical implications of defects in inosine modification will be reviewed. The most salient insights are that: (1) inosine at position 34 (the first position in the anticodon) is not universally present in the tree of life; (2) in many bacteria just a single homodimeric enzyme (TadA) is responsible for both tRNA inosine modification and mRNA inosine modification; (3) rapid progress is currently being made both in the molecular understanding of the heterodimeric ADAT2/ADAT3 enzyme responsible for inosine modifications in eukaryotes and in experimental capabilities for monitoring both the cytoplasmic tRNA pool and their modifications; (4) for selected tRNAs, inosine modification at position 37 has been demonstrated but this modification remains under-studied; (5) modification of tRNAs known to contain inosine can be incomplete; (6) the GC content of the T-stem is of great importance for wobble behavior, including wobbling behavior of inosine; and (7) the tRNA inosine modification is of direct relevance to human disease. In summary, research on inosine continues to yield important novel insights.

关键词： Inosine Wobble Modopathies Eukaryogenesis Nanopore ADAT Adenosine deaminase acting on tRNA CDAT Cytosine deaminase acting on tRNA FECA First eukaryote common ancestor I Inosine LACA Last archaeal common ancestor LBCA Last bacterial common ancestor LECA Last eukaryote common ancestor LUCA Last universal common ancestor Ψ Pseudourine TAD tRNA-specific Adenosine Deaminase

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：