排序方式: 共有75条查询结果,搜索用时 15 毫秒
1.
An identifying code is a subset of vertices of a graph with the property that each vertex is uniquely determined (identified) by its nonempty neighbourhood within the identifying code. When only vertices out of the code are asked to be identified, we get the related concept of a locating-dominating set. These notions are closely related to a number of similar and well-studied concepts such as the one of a test cover. In this paper, we study the decision problems Identifying Code and Locating-Dominating Set (which consist in deciding whether a given graph admits an identifying code or a locating-dominating set, respectively, with a given size) and their minimization variants Minimum Identifying Code and Minimum Locating-Dominating Set. These problems are known to be NP-hard, even when the input graph belongs to a number of specific graph classes such as planar bipartite graphs. Moreover, it is known that they are approximable within a logarithmic factor, but hard to approximate within any sub-logarithmic factor. We extend the latter result to the case where the input graph is bipartite, split or co-bipartite: both problems remain hard in these cases. Among other results, we also show that for bipartite graphs of bounded maximum degree (at least 3), the two problems are hard to approximate within some constant factor, a question which was open. We summarize all known results in the area, and we compare them to the ones for the related problem Dominating Set. In particular, our work exhibits important graph classes for which Dominating Set is efficiently solvable, but Identifying Code and Locating-Dominating Set are hard (whereas in all previous works, their complexity was the same). We also introduce graph classes for which the converse holds, and for which the complexities of Identifying Code and Locating-Dominating Set differ. 相似文献
2.
《Operations Research Letters》2019,47(6):494-501
We prove that testing feasibility for an AC power flow system is a strongly NP-hard problem. 相似文献
3.
Janina A. Brenner Sándor P. Fekete Jan C. van der Veen 《Mathematical Methods of Operations Research》2009,69(2):281-296
We consider a special case of the directed subgraph homeomorphism or topological minor problem, where the host graph has a
specific regular structure. Given an acyclic directed pattern graph, we are looking for a host graph of minimal height which
still allows for an embedding. This problem has applications in compiler design for certain coarse-grain reconfigurable architectures.
In this application domain, the task is to simultaneously schedule, bind and route a so-called data-flow graph, where vertices represent operations and arcs stand for data dependencies between the operations, given an orthogonal
grid structure of reconfigurable processing elements (PEs) that have restricted communication abilities. We show that the
problem of simultaneously scheduling, binding and routing is NP-complete by describing a logic engine reduction from NAE-3-SAT.
This result holds even when the input graph is a directed tree with maximum indegree two. We also give a |V|3/2-approximation algorithm.
J. A. Brenner’s research supported by the DFG Research Center Matheon “Mathematics for key technologies”.
J. C. van der Veen’s research supported by DFG Focus Program 1148, “Reconfigurable Architectures”, Grants FE 407/8-1 and FE
407/8-2. 相似文献
4.
Zoltán Király 《Discrete Applied Mathematics》2010,158(6):723-727
We consider a local edge-connectivity hypergraph augmentation problem. Specifically, we are given a hypergraph G=(V,E) and a subpartition of V. We are asked to find the smallest possible integer γ, for which there exists a set of size-two edges F, with |F|=γ, such that in G′=(V,E∪F), the local edge-connectivity between any pair of vertices lying in the same part of the subpartition is at least a given value k. Using a transformation from the bin-packing problem, we show that the associated decision problem is NP-complete, even when k=2. 相似文献
5.
We give new bounds on the star arboricity and the caterpillar arboricity of planar graphs with given girth. One of them answers an open problem of Gyárfás and West: there exist planar graphs with track number 4. We also provide new NP-complete problems. 相似文献
6.
An induced matching of a graph G is a matching having no two edges joined by an edge. An efficient edge dominating set of G is an induced matching M such that every other edge of G is adjacent to some edge in M. We relate maximum induced matchings and efficient edge dominating sets, showing that efficient edge dominating sets are maximum induced matchings, and that maximum induced matchings on regular graphs with efficient edge dominating sets are efficient edge dominating sets. A necessary condition for the existence of efficient edge dominating sets in terms of spectra of graphs is established. We also prove that, for arbitrary fixed p≥3, deciding on the existence of efficient edge dominating sets on p-regular graphs is NP-complete. 相似文献
7.
Jie Wang 《Journal of Complexity》2002,18(4):1024
We present in this paper a dynamic binary coding scheme α on CNF formulas ψ, and show that under a uniform distribution μα on binary string α(ψ), SAT is complete on average, where μα(ψ) is proportional to α(ψ)−22−α(ψ). We then show that there is k0>2 such that for all kk0, kSAT under μα is complete on average. 相似文献
8.
Kazuhisa Makino Yushi Uno Toshihide Ibaraki 《Journal of Algorithms in Cognition, Informatics and Logic》2001,38(2):411
In this paper, we introduce the problem of computing a minimum edge ranking spanning tree (MERST); i.e., find a spanning tree of a given graph G whose edge ranking is minimum. Although the minimum edge ranking of a given tree can be computed in polynomial time, we show that problem MERST is NP-hard. Furthermore, we present an approximation algorithm for MERST, which realizes its worst case performance ratio
where n is the number of vertices in G and Δ* is the maximum degree of a spanning tree whose maximum degree is minimum. Although the approximation algorithm is a combination of two existing algorithms for the restricted spanning tree problem and for the minimum edge ranking problem of trees, the analysis is based on novel properties of the edge ranking of trees. 相似文献
10.
Dirk Müller 《Mathematical Programming》2006,105(2-3):275-288
The edge-disjoint paths problem and many special cases of it are known to be NP-complete. We present a new NP-completeness
result for a special case of the problem, namely the directed edge-disjoint paths problem restricted to planar supply graphs
and demand graphs consisting of two sets of parallel edges. 相似文献