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

Total tessellation cover: Bounds, hardness, and applications

DISCRETE APPLIED MATHEMATICS 2022年 323卷 149-161页

作者： Abreu, Alexandre Cunha, Luis Figueiredo, Celina Marquezino, Franklin Posner, Daniel Portugal, Renato Univ Fed Rio de Janeiro Rio De Janeiro Brazil Fundacao Getulio Vargas Rio De Janeiro Brazil Univ Fed Fluminense Niteroi Brazil Univ Fed Rural Rio de Janeiro Seropedica Brazil Lab Nacl Comp Cient Petropolis Brazil

The concept of graph tessellation cover was defined in the context of quantum walk models, and is a current research area in graph theory. In this work, we propose a generalization called total tessellation cover. A tessellation of a graph G is a partition of its vertex set V(G) into vertex disjoint cliques. A tessellation cover of G is a set of tessellations that covers its edge set E(G). A total tessellation cover of G consists of a tessellation cover together with a compatible vertex coloring, such that the color of each vertex is different from the tessellation labels of the edges incident to the vertex. The total tessellation cover number Tt(G) is the size of a minimum total tessellation cover of G. We present lower bounds Tt(G) > omega(G) and Tt(G) > s(G) + 1, where omega(G) is the size of a maximum clique, and s(G) is the number of edges of a maximum induced star subgraph. A graph G is called a good total tessellable if Tt(G) = omega(G) or Tt(G) = s(G)+ 1. We study the complexity of the k -TOTAL TESSELLABILITy problem, which aims to decide whether a given graph G has Tt(G) < k. We prove that k -TOTAL TESSELLABILITy is in P for good total tessellable graphs. We establish the NP-completeness of the k -TOTAL TESSELLABILITy when restricted to the following graph classes: bipartite graphs, line graphs of triangle-free graphs, universal graphs, (2, 1)-chordal graphs and planar graphs.(c) 2021 Elsevier B.V. All rights reserved.

关键词： Graph tessellation Graph coloring algorithms and complexity Quantum walks

来源：评论

学校读者我要写书评

暂无评论

Temporal interval cliques and independent sets

引用

THEORETICAL COMPUTER SCIENCE 2023年第1期961卷

作者： Hermelin, Danny Itzhaki, Yuval Molter, Hendrik Niedermeier, Rolf Bengurion Univ Negev POB 653 IL-8410501 Beer Sheva Israel TU Berlin Str 17 Juni 135 D-10623 Berlin Germany

Temporal graphs have been recently introduced to model changes in a given network that occur throughout a fixed period of time. The TEMPORAL A CLIQUE problem, which generalizes the well known CLIQUE problem to temporal graphs, has been studied in the context of finding nodes of interest in dynamic networks [TCS '16]. We introduce the TEMPORAL A INDEPENDENT SET problem, a temporal generalization of INDEPENDENT SET. This problem is e.g. motivated in the context of finding conflict-free schedules for maximum subsets of tasks, that have certain (time-varying) constraints within a given time period. We are specifically interested in the case where each task needs to be performed in a certain time-interval on each day and two tasks are in conflict on a certain day if their time-intervals on that day overlap. This leads us to consider both problems on the restricted class of temporal unit interval graphs, i.e., temporal graphs where each layer is a unit interval graph. We present several hardness results as well as positive results. On the algorithmic side, we provide constant-factor approximation algorithms for instances of both problems where t, the total number of time steps (layers) of the temporal graph, and A, a parameter that allows us to model conflict tolerance, are constants. We develop an exact FPT algorithm for TEMPORAL A CLIQUE with respect to parameter t + k. Finally, we use the notion of order preservation for temporal unit interval graphs that, informally, requires the intervals of every layer to obey a common ordering. For both problems, we provide an FPT algorithm parameterized by the size of minimum vertex deletion set to order preservation.(c) 2023 Elsevier B.V. All rights reserved.

关键词： Temporal graphs Vertex orderings Order preservation Interval graphs algorithms and complexity

来源：评论

学校读者我要写书评

暂无评论

Computing and testing Pareto optimal committees

引用

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS 2020年第1期34卷 1-20页

作者： Aziz, Haris Monnot, Jerome UNSW Sydney Sydney NSW 2052 Australia Data61 CSIRO Sydney NSW 2052 Australia Univ Paris 09 LAMSADE Paris France

Selecting a set of alternatives based on the preferences of agents is an important problem in committee selection and beyond. Among the various criteria put forth for desirability of a committee, Pareto optimality is a minimal and important requirement. As asking agents to specify their preferences over exponentially many subsets of alternatives is practically infeasible, we assume that each agent specifies a weak order on single alternatives, from which a preference relation over subsets is derived using some preference extension. We consider five prominent extensions (responsive, downward lexicographic, upward lexicographic, best, and worst). For each of them, we consider the corresponding Pareto optimality notion, and we study the complexity of computing and verifying Pareto optimal outcomes. For each of the preference extensions, we give a complete characterization of the complexity of testing Pareto optimality when preferences are dichotomous or linear. We also consider strategic issues: for four of the set extensions, we present a linear-time, Pareto optimal and strategyproof algorithm that even works for weak preferences.

关键词： Committee selection Multiwinner voting Pareto optimality algorithms and complexity Set extensions

来源：评论

学校读者我要写书评

暂无评论

DNA combinatorial messages and Epigenomics: The case of chromatin organization and nucleosome occupancy in eukaryotic genomes

引用

THEORETICAL COMPUTER SCIENCE 2019年 792卷 117-130页

作者： Giancarlo, Raffaele Rombo, Simona E. Utro, Filippo Univ Palermo Dipartimento Matemat & Informat Via Archirafi 34 I-90123 Palermo Italy IBM TJ Watson Res Computat Biol Ctr Yorktown Hts NY 10598 USA

Epigenomics is the study of modifications on the genetic material of a cell that do not depend on changes in the DNA sequence, since those latter involve specific proteins around which DNA wraps. The end result is that Epigenomic changes have a fundamental role in the proper working of each cell in Eukaryotic organisms. A particularly important part of Epigenomics concentrates on the study of chromatin, that is, a fiber composed of a DNA-protein complex and very characterizing of Eukaryotes. Understanding how chromatin is assembled and how it changes is fundamental for Biology. In more than thirty years of research in this area, Mathematics and Theoretical Computer Science have gained a prominent role, in terms of modeling and mining, regarding in particular the so-called 10 nm fiber. Starting from some very basic notions of Biology, we briefly illustrate the recent advances obtained via laboratory experiments on the organization and dynamics of chromatin. Then, we mainly concentrate our attention on the contributions given by Combinatorial and Informational Methodologies, that are at the hearth of Theoretical Computer Science, to the understanding of mechanisms determining the 10 nm fiber. We conclude highlighting several directions of investigation that are perceived as important and where Theoretical Computer Science can provide high impact results. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Computational biology algorithms and complexity Formal languages Combinatorics on words

来源：评论

学校读者我要写书评

暂无评论

Low-Cost Wearable Technology Model to Control and Monitor Chronic Diseases for Healthcare 25

Low-Cost Wearable Technology Model to Control and Monitor Ch...

引用

25th IEEE International Conference on Electronics, Electrical Engineering and Computing (INTERCON)

作者： Pumajulca-Salazar, Alcibiades Mac-Choy, Jorge Armas-Aguirre, Jimmy Univ Peruana Ciencias Aplicadas Informat Syst Engn Lima Peru

ISBN: (纸本)9781538654903

In this paper, we propose a low-cost wearable technology model to control and monitor chronic diseases for healthcare. We enhance prior models by focusing on low cost components, and we assess the current hardware and systems applications offered in the market. Our proposed model also emphasizes the application of real-time data analysis for the healthcare organization. The model consists of six components: 1. Data acquisition;2. Data Processing;3. Information Results;4. Decision making Support;5. Technology Platform;6. Framework for personal data protection. The model was validated with a group of 12 females over 70 years who were diagnosed with tumors at different stages. The preliminary results show that the mean temperature difference between the armpits and malignant tumors is 0.7 +/- 0.5, while the mean temperature difference between the armpits and benign tumors is 2.1 +/- 0.5.

关键词： Low-Cost Wearable Chronic Disease Tumor algorithms and complexity Intelligent Systems Social Issues and Professional Practice Signal and Image Processing Control Systems

来源：评论

学校读者我要写书评

暂无评论

Partial-order Algorithm of Model Checking in μ-Predicate Ambient Logic

引用

电脑学刊 2018年第5期29卷 142-159页

作者： Hua Jiang Rong-De Lin Fu-Min Zou Ling-Xiang Li

This paper introduces a kind of partial-order algorithm of model-checking in finitecontrol mobile ambients against μ-predicate ambient logic (Ambient logic based on first-order μ- calculus). Based on Tarski's fixpoint theorem, nested predicate equations and Block Dependency Graph, a group of partial ordering relation between inter-mediate results in the process of model checking is given, and thus a kind of local model-checking algorithm is proposed. To our knowledge, this is the first algorithm which exponent of time complexity is d/2+2, the exponent of space complexity is d/2 (d is the alternate nesting depth of fixpoint operator in the formula) and this is the third model-checking algorithm for predicate ambient logic with recursion. This paper's contributions are: (1) getting a group of partial ordering relation between intermediate results in the computing process of model checking for μ- calculus first-order predicate ambient logic based on Tarski's fixpoint theorem; (2) using the partial ordering relation to design an algorithm for model checking in mobile ambients; (3) analyzing the complexity of the algorithm.

关键词： algorithms and complexity mobile ambient model checking predicate ambient logic

来源：评论

学校读者我要写书评

暂无评论

Possible Bribery in k-Approval and k-Veto Under Partial Information 17th

Possible Bribery in <i>k</i>-Approval and <i>k</i>-Veto Unde...

引用

17th International Conference on Artificial Intelligence - Methodology, Systems and Applications (AIMSA)

作者： Erdelyi, Gabor Reger, Christian Univ Siegen Unteres Schloss 3 D-57072 Siegen Germany

ISBN: (纸本)9783319447483;9783319447476

We study the complexity of possible bribery under nine different notions of partial information for k-Approval and k-Veto. In bribery an external agent tries to change the outcome of an election by changing some voters' votes. Usually in voting theory, full information is assumed, i.e., the manipulative agent knows the set of candidates, the complete ranking of each voter about the candidates and the voting rule used. In this paper, we assume that the briber only has partial information about the voters' votes and ask whether the briber can change some voters' votes such that there is a completion of the partial profile to a full profile such that the briber's preferred candidate (or most despised candidate in the destructive case) is a winner (not a winner) of the resulting election.

关键词： Computational social choice Voting algorithms and complexity

来源：评论

学校读者我要写书评

暂无评论

Dichotomy results for fixed point counting in boolean dynamical systems

引用

THEORETICAL COMPUTER SCIENCE 2015年 573卷 16-25页

作者： Homan, Christopher M. Kosub, Sven Rochester Inst Technol Dept Comp Sci Rochester NY 14623 USA Univ Konstanz Dept Comp & Informat Sci D-78457 Constance Germany

We present dichotomy theorems regarding the computational complexity of counting fixed points in boolean (discrete) dynamical systems, i.e., finite discrete dynamical systems over the domain {0, 1). For a class F of boolean functions and a class G of graphs, an (F, G)-system is a boolean dynamical system with local transitions functions lying in F and graphs in G. We show that, if local transition functions are given by lookup tables, then the following complexity classification holds: Let F be a class of boolean functions closed under superposition and let G be a graph class closed under taking minors. If F contains all min-functions, all max-functions, or all self-dual and monotone functions, and G contains all planar graphs, then it is #P-complete to compute the number of fixed points in an (F, G)-system;otherwise it is computable in polynomial time. We also prove a dichotomy theorem for the case that local transition functions are given by formulas (over logical bases). This theorem has a significantly more complicated structure than the theorem for lookup tables. A corresponding theorem for boolean circuits coincides with the theorem for formulas. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Discrete dynamical systems Fixed point algorithms and complexity

来源：评论

学校读者我要写书评

暂无评论

The complexity of manipulative attacks in nearly single-peaked electorates

引用

ARTIFICIAL INTELLIGENCE 2014年第1期207卷 69-99页

作者： Faliszewski, Piotr Hemaspaandra, Edith Hemaspaandra, Lane A. AGH Univ Sci & Technol Dept Comp Sci Krakow Poland Rochester Inst Technol Dept Comp Sci Rochester NY 14623 USA Univ Rochester Dept Comp Sci Rochester NY 14627 USA

Many electoral control and manipulation problems-which we will refer to in general as "manipulative actions" problems-are NP-hard in the general case. It has recently been noted that many of these problems fall into polynomial time if the electorate is single-peaked, i.e., is polarized along some axis/issue. However, real-world electorates are not truly single-peaked. There are usually some mavericks, and so real-world electorates tend merely to be nearly single-peaked. This paper studies the complexity of manipulative-action algorithms for elections over nearly single-peaked electorates. We do this for many notions of nearness and for a broad range of election systems. We provide instances where even one maverick jumps the manipulative-action complexity up to NP-hardness, but we also provide many instances where some number of mavericks can be tolerated without increasing the manipulative-action complexity. (C) 2013 Elsevier B.V. All rights reserved.

关键词： algorithms and complexity Computational social choice Election control/manipulation Multiagent systems Nearly single-peaked preferences

来源：评论

学校读者我要写书评

暂无评论

Elimination for Generic Sparse Polynomial Systems

引用

DISCRETE & COMPUTATIONAL GEOMETRY 2014年第3期51卷 578-599页

作者： Isabel Herrero, Maria Jeronimo, Gabriela Sabia, Juan Univ Buenos Aires Fac Ciencias Exactas & Nat Dept Matemat RA-1428 Buenos Aires DF Argentina Univ Buenos Aires Dept Ciencias Exactas RA-1428 Buenos Aires DF Argentina CONICET UBA IMAS Buenos Aires DF Argentina

We present a new probabilistic symbolic algorithm that, given a variety defined in an n-dimensional affine space by a generic sparse system with fixed supports, computes the Zariski closure of its projection to an a""-dimensional coordinate affine space with a""< n. The complexity of the algorithm depends polynomially on some combinatorial invariants associated to the supports.

关键词： Projection of algebraic varieties Sparse polynomial systems algorithms and complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：