A weak dominance drawing Gamma of a DAG G = (V,E) is a d-dimensional drawing such that D(u) < D(v) for every dimension D of Gamma if there is a directed path from a vertex u to a vertex v in G, where D(w) is the co...
详细信息
A weak dominance drawing Gamma of a DAG G = (V,E) is a d-dimensional drawing such that D(u) < D(v) for every dimension D of Gamma if there is a directed path from a vertex u to a vertex v in G, where D(w) is the coordinate of vertex w is an element of V in dimension D of Gamma. If D(u) < D(v) for every dimension D of Gamma, but there is no path from u to v, we have a falsely implied path (fip). Minimizing the number of fips is an important theoretical and practical problem. Computing 2-dimensional weak dominance drawings with minimum number of fips is NP-hard. We show that this problem is fpt parameterized by the dimension d and the modular width mw. A key ingredient of our proof is the Compaction Lemma, where we show an interesting property of any weak dominance drawing of G with the minimum number of fips. This fpt result in weak dominance, which is interesting by itself because the fip-minimization problem is NP-hard, is used to prove our main contributions. Computing the dominance dimension of G, that is, the minimum number of dimensions d for which G has a d-dimensional dominance drawing (a weak dominance drawing with 0 fips), is a well-known NP-hard problem. We show that the dominance dimension of G is bounded by mw/2 (or mw, if mw < 4) and that computing the dominance dimension of G is an fpt problem with parameter mw. As far as we know, this the first fpt-algorithm to compute the dominance dimension of a DAG.
In the {CLAW, DIAMOND}-FREE EDGE DELETION PROBLEM (CDFED), we are given a graph G and an integer k > 0, and the question is whether there are at most k edges whose deletion results in a graph without claws and diam...
详细信息
In the {CLAW, DIAMOND}-FREE EDGE DELETION PROBLEM (CDFED), we are given a graph G and an integer k > 0, and the question is whether there are at most k edges whose deletion results in a graph without claws and diamonds as induced subgraphs. Based on some refined observations, we propose a kernel of O (k(3)) vertices and O (k(4)) edges, significantly improving the previous kernel of O (k(12)) vertices and O (k(24)) edges. In addition, we derive an O*(3.792(k))-time algorithm for CDFED. (C) 2022 Elsevier B.V. All rights reserved.
Chvátal and Klincsek (1980) gave an O(n3)-time algorithm for the problem of finding a maximum-cardinality convex subset of an arbitrary given set P of n points in the plane. This paper examines a generalization o...
详细信息
A weak dominance drawing Gamma of a DAG G = (V, E) is a d-dimensional drawing such that D(u) < D(v) for every dimension D of Gamma if there is a directed path from a vertex u to a vertex v in G, where D(w) is the c...
详细信息
ISBN:
(纸本)9783031231001;9783031231018
A weak dominance drawing Gamma of a DAG G = (V, E) is a d-dimensional drawing such that D(u) < D(v) for every dimension D of Gamma if there is a directed path from a vertex u to a vertex v in G, where D(w) is the coordinate of vertex w is an element of V in dimension D of Gamma. If D(u) < D(v) for every dimension D of Gamma, but there is no path from u to v, we have a falsely implied path (fip). Minimizing the number of fips is an important theoretical and practical problem, which is NP-hard. We show that it is an fpt problem for graphs having bounded modular width mw and when d is bounded. This result in weak dominance, which is interesting by itself, lets us prove our main contributions. Computing the dominance dimension of G, that is, the minimum number of dimensions for which G has a dominance drawing (a weak dominance drawing with 0 fips), is a well-known NP-hard problem. We show that the dominance dimension of G is bounded by mw/2 (mw, if mw < 4) and that computing the dominance dimension of G is an fpt problem with parameter mw.
In this paper the NP-hard Maximum Clique Problem (MCP) is considered. It is supposed that the input graph is sparse. Also, it is believed that the input graph can have a huge number of vertices. A biphasic algorithm f...
详细信息
ISBN:
(纸本)9783319136714;9783319136707
In this paper the NP-hard Maximum Clique Problem (MCP) is considered. It is supposed that the input graph is sparse. Also, it is believed that the input graph can have a huge number of vertices. A biphasic algorithm for finding the exact solution of the MCP is proposed in the paper. The first phase of the algorithm is the preprocessing of the input graph by decomposing it into atoms. The second phase of the algorithm reduces to an application for each atom classical algorithm Wilf and then to the formation of solutions for the graph as a whole. The level of sparseness of the input graph is given in the form of restrictions on its treewidth. It have been proved that the running time of biphasic algorithm is polynomial in the number of vertices and the exponential of the treewidth of the input graph.
暂无评论