A cycle in a graph G is isometric if the distance between two vertices in the cycle is equal to their distance in G. Finding the longest isometric cycle of a graph is then a natural variant of the problem of finding a...
详细信息
A cycle in a graph G is isometric if the distance between two vertices in the cycle is equal to their distance in G. Finding the longest isometric cycle of a graph is then a natural variant of the problem of finding a longest cycle. While most variants of the longest cycle problem are NP-complete, we show that quite surprisingly, one can find a longest isometric cycle in a graph in polynomialtime. (C) 2008 Elsevier B.V. All rights reserved.
We model a road network as a directed graph G = (V, E) with a source s and a sink t, where each edge e has a positive length l(e) and each vertex v has a distribution function alpha(v) with respect to the traffic ente...
详细信息
We model a road network as a directed graph G = (V, E) with a source s and a sink t, where each edge e has a positive length l(e) and each vertex v has a distribution function alpha(v) with respect to the traffic entering and leaving v. This paper proposes a polynomial time algorithm for evaluating the importance of each edge e is an element of E which is defined to be the traffic f(e) passing through e in order to assign the required traffic F-st(> 0) from a to t along only shortest s-t paths in accordance with the distribution function alpha(v) at each vertex v.
The reliability of capacity-limited networks subject to are failures can be evaluated by the mean value of maximum flow. Calculating the mean value of maximum flow is NP-hard. However, the Onaga upper bound sometimes ...
详细信息
The reliability of capacity-limited networks subject to are failures can be evaluated by the mean value of maximum flow. Calculating the mean value of maximum flow is NP-hard. However, the Onaga upper bound sometimes gives the exact value, eg, when graphs are bipartite. This paper gives for networks (whether arcs are directed or not) a necessary and sufficient condition for the Onaga upper bound to be exact.
A fully odd K-4 is a subdivision of K-4 such that each of the six edges of the K-4 is subdivided into a path of odd length. In 1974, Toft conjectured that every graph containing no fully odd K-4 can be vertex-colored ...
详细信息
A fully odd K-4 is a subdivision of K-4 such that each of the six edges of the K-4 is subdivided into a path of odd length. In 1974, Toft conjectured that every graph containing no fully odd K-4 can be vertex-colored with three colors. The purpose of this paper is to prove Toft's conjecture.
The maximum weight independent set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. Being one of the most investigated and most important problems o...
详细信息
The maximum weight independent set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. Being one of the most investigated and most important problems on graphs, it is well known to be NP-complete and hard to approximate. The complexity of MWIS is open for hole-free graphs (i.e., graphs without induced subgraphs isomorphic to a chordless cycle of length at least five). By applying clique separator decomposition as well as modular decomposition, we obtain polynomialtime solutions of MWIS for odd-hole- and dart-free graphs as well as for odd-hole- and bull-free graphs (dart and bull have five vertices, say , and dart has edges , while bull has edges ). If the graphs are hole-free instead of odd-hole-free then stronger structural results and better time bounds are obtained.
We look at several variations of the single fault detection problem for combinational logic circuits and show that deciding whether single faults are detectable by input-output (I/O) experiments is polynomially comple...
详细信息
We look at several variations of the single fault detection problem for combinational logic circuits and show that deciding whether single faults are detectable by input-output (I/O) experiments is polynomially complete, i.e., there is a polynomial time algorithm to decide if these single faults are detectable if and only if there is a polynomial time algorithm for problems such as the traveling salesman problem, knapsack problem, etc.
New calculation procedures for finding the probabilities of state transitions of the system in discrete Markov processes based on dynamic programming are developed and polynomial time algorithms for determining the li...
详细信息
New calculation procedures for finding the probabilities of state transitions of the system in discrete Markov processes based on dynamic programming are developed and polynomial time algorithms for determining the limit state matrix in such processes are proposed. Computational complexity aspects and possible applications of the proposed algorithms for the stochastic optimization problems are characterized.
作者：
TCHUENTE, MCNRS-IMAG
Laboratoire TIM3 BP 68 38402 Saint Martin d'Hères Cedex France
We are interested in the minimum time T ( S ) necessary for computing a family S = { : − S i , S j ϵ R p , ( i , j ) ϵ E } of inner products of order p , on a systolic array of order p × 2. We first prove that th...
详细信息
We are interested in the minimum time T ( S ) necessary for computing a family S = { < S i , S j >: − S i , S j ϵ R p , ( i , j ) ϵ E } of inner products of order p , on a systolic array of order p × 2. We first prove that the determination of T ( S ) is equivalent to the partition problem and is thus NP-complete. Then we show that the designing of an algorithm which runs in time T ( S ) + 1 is equivalent to the problem of finding an undirected bipartite eulerian multigraph with the smallest number of edges, which contains a given undirected bipartite graph, and can therefore be solved in polynomialtime.
Let G be an Eulerian digraph, and let {x(1), x(2)}, {y(1), y(2)} be two pairs of vertices in G. A directed path from a vertex s to a vertex t is called an st-path. An instance (G;{x(1);x(2)}, {y(1), y(2)}) is called f...
详细信息
Let G be an Eulerian digraph, and let {x(1), x(2)}, {y(1), y(2)} be two pairs of vertices in G. A directed path from a vertex s to a vertex t is called an st-path. An instance (G;{x(1);x(2)}, {y(1), y(2)}) is called feasible if there is a choice of h, i, j, k with {h, i} = { j, k} = {1, 2} such that G has two arc-disjoint x(h) x(i)- and y(j) y(k)-paths. In this paper, we characterize the structure of minimal infeasible instances, based on which an O(m + n log n) timealgorithm is presented to decide whether a given instance is feasible, where n and m are the number of vertices and arcs in the instance, respectively. If the instance is feasible, the corresponding two arc-disjoint paths can be computed in O(m(m + n log n)) time.
We consider the problem of clique coloring, that is, coloring the vertices of a given graph such that no (maximal) clique of size at least two is monocolored. It is known that interval graphs are 2-clique colorable. I...
详细信息
We consider the problem of clique coloring, that is, coloring the vertices of a given graph such that no (maximal) clique of size at least two is monocolored. It is known that interval graphs are 2-clique colorable. In this paper we prove that B-1-EPG graphs (edge intersection graphs of paths on a grid, where each path has at most one bend) are 4-clique colorable. Moreover, given a B1-EPG representation of a graph, we provide a linear timealgorithm that constructs a 4-clique coloring of it. (C) 2017 Elsevier B.V. All rights reserved.
暂无评论