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

NP-HARDNESS AND FIXED-PARAMETER TRACTABILITY OF REALIZING DEGREE SEQUENCES WITH DIRECTED ACYCLIC GRAPHS

SIAM JOURNAL ON DISCRETE MATHEMATICS 2015年第4期29卷 1931-1960页

作者： Hartung, Sepp Nichterlein, Andre TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany

In graph realization problems, one is given a degree sequence and the task is to decide whether there is a graph whose vertex degrees match the given sequence. This realization problem is known to be polynomial-time solvable when the graph is directed or undirected. In contrast, we show NP-completeness for the problem of realizing a given sequence of pairs of nonnegative integers (representing in-and outdegrees) with a directed acyclic graph (DAG), answering an open question of Berger and Muller-Hannemann. Furthermore, we classify the problem as fixed-parameter tractable with respect to the parameter "maximum degree." Investigating sparse and dense settings, we show that the problem remains NP-hard even if the realizing DAG (precisely, the underlying undirected graph) can be transformed into a clique (a tree) by adding (deleting) a constant fraction of the arcs. In contrast, if at most k arcs have to be inserted, respectively, removed to obtain a clique or a tree in the underlying undirected graph, then the problem becomes fixed-parameter tractable with respect to k.

关键词： graph realization problems combinatorial algorithms parameterized complexity structural parameterization

来源：评论

学校读者我要写书评

暂无评论

Submodular Relaxation for Inference in Markov Random Fields

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2015年第7期37卷 1347-1359页

作者： Osokin, Anton Vetrov, Dmitry P. INRIA SIERRA Team Paris France Ecole Normale Super F-75231 Paris France Higher Sch Econ Fac Comp Sci Moscow Russia Moscow MV Lomonosov State Univ Moscow Russia

In this paper we address the problem of finding the most probable state of a discrete Markov random field (MRF), also known as the MRF energy minimization problem. The task is known to be NP-hard in general and its practical importance motivates numerous approximate algorithms. We propose a submodular relaxation approach (SMR) based on a Lagrangian relaxation of the initial problem. Unlike the dual decomposition approach of Komodakis et al. [29] SMR does not decompose the graph structure of the initial problem but constructs a submodular energy that is minimized within the Lagrangian relaxation. Our approach is applicable to both pairwise and high-order MRFs and allows to take into account global potentials of certain types. We study theoretical properties of the proposed approach and evaluate it experimentally.

关键词： Markov random fields energy minimization combinatorial algorithms relaxation graph cuts

来源：评论

学校读者我要写书评

暂无评论

Sorting Linear Genomes with Rearrangements and Indels

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2015年第3期12卷 500-506页

作者： Braga, Marilia D. V. Stoye, Jens Inmetro Inst Nacl Metrol Qualidade & Tecnol Rio De Janeiro Brazil Univ Bielefeld Fac Technol Bielefeld Germany Univ Bielefeld Ctr Biotechnol Bielefeld Germany

Rearrangements are mutations that can change the organization of a genome, but not its content. Examples are inversions of DNA segments, translocations of chromosome ends, fusions and fissions of chromosomes. All mentioned rearrangements can be represented by the generic Double Cut and Join (DCJ) operation. However, the DCJ operation also allows circular chromosomes to be created at intermediate steps, even if the compared genomes are linear. In this case it is more plausible to consider a restriction in which the reincorporation of a circular chromosome has to be done immediately after its creation. We call these two consecutive operations an ER composition. It has been shown that an ER composition mimics either an internal block interchange (when two segments in the same chromosome exchange their positions), or an internal transposition (the special case of a block interchange when the two segments are adjacent). The DCJ distance of two genomes is the same, regardless of this restriction, and can be computed in linear time. For comparing two genomes with unequal contents, in addition to rearrangements we have to allow insertions and deletions of DNA segments-named indels. It is already known that the distance in the model combining DCJ and indel operations can be exactly computed. Again, for linear genomes it would be more plausible to adopt a restricted version with ER compositions. This model was studied recently by da Silva et al. (BMC Bioinformatics 13, Suppl. 19, S14, 2012), but only an upper bound for the restricted DCJ-indel distance was provided. Here we first solve an open problem posed in that paper and present a very simple proof showing that the distance, which can be computed in linear time, is the same for both the unrestricted and the restricted DCJ-indel models. We then give a simpler algorithm for computing an optimal restricted DCJ-indel sorting scenario in O(n log n) time. We also relate the DCJ-indel distance to the restricted DCJ-substitution

关键词： combinatorial algorithms bioinformatics comparative genomics genome rearrangement double cut and join

来源：评论

学校读者我要写书评

暂无评论

NETWORK-BASED VERTEX DISSOLUTION

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2015年第2期29卷 888-914页

作者： Van Bevern, Rene Bredereck, Robert Chen, Jiehua Froese, Vincent Niedermeier, Rolf Woeginger, Gerhard J. TU Berlin Inst Softwaretech & Theoret Informat D-10587 Berlin Germany TU Eindhoven Dept Math & Comp Sci NL-5600 MB Eindhoven Netherlands

We introduce a graph-theoretic vertex dissolution model that applies to a number of redistribution scenarios, such as gerrymandering in political districting or work balancing in an online situation. The central aspect of our model is the deletion of certain vertices and the redistribution of their load to neighboring vertices in a completely balanced way. We investigate how the underlying graph structure, the knowledge of which vertices should be deleted, and the relation between old and new vertex loads influence the computational complexity of the underlying graph problems. Our results establish a clear borderline between tractable and intractable cases.

关键词： computational complexity analysis combinatorial algorithms economization election control flow networks matching NP-hard problems political districting redistribution scenarios

来源：评论

学校读者我要写书评

暂无评论

Upward planarity testing in practice: SAT formulations and comparative study

引用

ACM Journal of Experimental Algorithmics 2015年第1期20卷 1–27页

作者： Chimani, Markus Zeranski, Robert Theoretical Computer Science Osnabrück University Osnabrück 49076 Germany Institute of Computer Science Friedrich-Schiller-University Jena Jena 07743 Germany

A directed acyclic graph (DAG) is upward planar if it can be drawn without any crossings while all edges-when following them in their direction-are drawn with strictly monotonously increasing y-coordinates. Testing whether a graph allows such a drawing is known to be NP-complete, and while the problem is polynomial-time solvable for special graph classes, there is not much known about solving the problem for general graphs in practice. The only attempt so far has been a branch-and-bound algorithm over the graph's triconnectivity structure, which was able to solve small graphs. Furthermore, there are some known FPT algorithms to deal with the problem. In this article, we propose two fundamentally different approaches based on the seemingly novel concept of ordered embeddings and on the concept of a Hanani-Tutte-type characterization of monotone drawings. In both approaches, we model the problem as special SAT instances, that is, logic formulae for which we check satisfiability. Solving these SAT instances allows us to decide upward planarity for arbitrary graphs. For the first time, we give an extensive experimental comparison between virtually all known approaches to the problem. To this end, we also investigate implementation issues and different variants of the known algorithms as well as of our SAT approaches and evaluate all algorithms on real-world as well as on constructed *** also give a detailed performance study of the novel SAT *** show that the SAT formulations outperform all known approaches for graphs with up to 400 edges. For even larger graphs, a modified branch-and-bound algorithm becomes competitive. © Versita Sp. z o.o.

关键词： combinatorial algorithms Experimental evaluation Graph drawing Implementations SAT formulation Upward planarity

来源：评论

学校读者我要写书评

暂无评论

Base-Station Positioning for Heterogeneous Systems with Coverage, Capacity and Cost Criteria

Base-Station Positioning for Heterogeneous Systems with Cove...

引用

European Conference On Networks And Communications (EuCNC)

作者： Athanasiadou, G. E. Tsoulos, G. V. Zarbouti, D. Univ Peloponnese Dept Informat & Telecommun Tripoli Greece

ISBN: (纸本)9781467373593

The problem of optimum base station positioning started with the deployment of the first cellular wireless systems, initially with coverage and traffic criteria. Nowadays, the increased demand for geographically inhomogeneous capacity leads to mixed cell structures as well as relay nodes, while the cost of the different deployments varies significantly. The characteristic of heterogeneous systems is that the optimum solution can be a small group of macrocells or a large number of microcells or anything in between. The algorithm presented in this paper has been developed for heterogeneous wireless systems, follows a combinatorial approach and the optimization analysis is based on coverage, capacity and cost criteria. Results demonstrate the flexible performance of the algorithm, as well as the tendency of the solutions towards the deployment of very small cells in order to satisfy the ever increasing capacity requirements.

关键词： Heterogeneous wireless systems Base-station positioning combinatorial algorithms

来源：评论

学校读者我要写书评

暂无评论

If the Current Clique algorithms are Optimal, so is Valiant's Parser 56

If the Current Clique Algorithms are Optimal, so is Valiant'...

引用

56th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Abboud, Amir Backurs, Arturs Williams, Virginia Vassilevska Stanford Univ Dept Comp Sci Palo Alto CA 94304 USA MIT EECS Cambridge MA 02139 USA

ISBN: (纸本)9781467381918

The CFG recognition problem is: given a context-free grammar G and a string w of length n, decide if w can be obtained from G. This is the most basic parsing question and is a core computer science problem. Valiant's parser from 1975 solves the problem in O(n(omega)) time, where omega < 2.373 is the matrix multiplication exponent. Dozens of parsing algorithms have been proposed over the years, yet Valiant's upper bound remains unbeaten. The best combinatorial algorithms have mildly subcubic O(n(3)/log(3) n) complexity. Lee (JACM'01) provided evidence that fast matrix multiplication is needed for CFG parsing, and that very efficient and practical algorithms might be hard or even impossible to obtain. Lee showed that any algorithm for a more general parsing problem with running time O(vertical bar G vertical bar center dot n(3-epsilon)) can be converted into a surprising subcubic algorithm for Boolean Matrix Multiplication. Unfortunately, Lee's hardness result required that the grammar size be vertical bar G vertical bar = Omega(n(6)). Nothing was known for the more relevant case of constant size grammars. In this work, we prove that any improvement on Valiant's algorithm, even for constant size grammars, either in terms of runtime or by avoiding the inefficiencies of fast matrix multiplication, would imply a breakthrough algorithm for the k-Clique problem: given a graph on n nodes, decide if there are k that form a clique. Besides classifying the complexity of a fundamental problem, our reduction has led us to similar lower bounds for more modern and well-studied cubic time problems for which faster algorithms are highly desirable in practice: RNA Folding, a central problem in computational biology, and Dyck Language Edit Distance, answering an open question of Saha (FOCS' 14).

关键词： context free grammars parsing CFG recognition clique conditional lower bounds RNA folding Dyck Edit Distance hardness in P tight hardness combinatorial algorithms Valiant's algorithm natural language processing parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

An Algorithmic-type Classification of Tetravalent One-regular Graphs Using Computer Algebra Tools

引用

FUNDAMENTA INFORMATICAE 2014年第3期135卷 211-228页

作者： Ghasemi, Mohsen Urmia Univ Dept Math Orumiyeh 57135 Iran

A finite graph is one-regular if its automorphism group acts regularly on the set of its arcs. In the present paper, tetravalent one-regular graphs of order 7p(2), where p is a prime, are classified using computer alg... 详细信息

关键词： s-transitive graphs symmetric graphs Cayley graphs magma combinatorial algorithms

来源：评论

学校读者我要写书评

暂无评论

Cyber Security Analysis of Power Networks by Hypergraph Cut algorithms

Cyber Security Analysis of Power Networks by Hypergraph Cut ...

引用

2014 IEEE International Conference on Smart Grid Communications (SmartGridComm)

作者： Yamaguchi, Yutaro Ogawa, Anna Takeda, Akiko Iwata, Satoru Univ Tokyo Dept Math Informat Tokyo Japan Keio Univ Dept Adm Engn Yokohama Kanagawa Japan

ISBN: (纸本)9781479949342

This paper presents exact solution methods for analyzing vulnerability of electric power networks to a certain kind of undetectable attacks known as false data injection attacks. We show that the problems of finding the minimum number of measurement points to be attacked undetectably reduce to minimum cut problems on hypergraphs, which admit efficient combinatorial algorithms. Experimental results indicate that our exact solution methods run as fast as the previous methods, most of which provide only approximate solutions. We also present the outline of an algorithm for enumerating all small cuts in a hypergraph, which can be used for finding vulnerable sets of measurement points.

关键词： distribution networks graph theory power system security transmission networks combinatorial algorithms cyber security analysis electric power networks false data injection attacks hypergraph cut algorithms solution methods Conferences Indexes Power measurement Security Smart grids Vectors Power grids electric power network transmission networks Smart grids Power system security Power measurement Graph theory hypergraph Network security

来源：评论

学校读者我要写书评

暂无评论

A strongly polynomial algorithm for generalized flow maximization 14

A strongly polynomial algorithm for generalized flow maximiz...

引用

46th Annual ACM Symposium on Theory of Computing (STOC)

作者： Vegh, Laszlo A. London Sch Econ & Polit Sci Dept Management London England

ISBN: (纸本)9781450327107

A strongly polynomial algorithm is given for the generalized flow maximization problem. It uses a new variant of the scaling technique, called continuous scaling. The main measure of progress is that within a strongly polynomial number of steps, an arc can be identified that must be tight in every dual optimal solution, and thus can be contracted.

关键词： generalized flows strongly polynomial algorithms linear programming combinatorial algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：