共查询到20条相似文献,搜索用时 31 毫秒
1.
M. C. Golumbic 《Computing》1977,18(3):199-208
Using the notion ofG-decomposition introduced in Golumbic [8, 9], we present an implementation of an algorithm which assigns a transitive orientation to a comparability graph inO(δ·|E|) time andO(|E|) space where δ is the maximum degree of a vertex and |E| is the number of edges. A quotient operation reducing the graph in question and preservingG-decomposition and transitive orientability is shown, and efficient solutions to a number ofNP-complete problems which reduce to polynomial time for comparability graphs are discussed. 相似文献
2.
Two flow network simplification algorithms 总被引:1,自引:0,他引:1
Flow network simplification can reduce the size of the flow network and hence the amount of computation performed by flow algorithms. We present the first linear time algorithm for the undirected network case. We also give an O(|E|∗(|V|+|E|)) time algorithm for the directed case, an improvement over the previous best O(|V|+2|E|log|V|) time solution. Both of our algorithms are quite simple. 相似文献
3.
M. Becker W. Degenhardt J. Doenhardt S. Hertel G. Kaninke W. Keber K. Mehlhorn S. Näher H. Rohnert T. Winter 《Information Processing Letters》1982,15(3):135-136
A probabilistic algorithm is presented which computes the vertex connectivity of an undirected graph G = (V,E) in expected time with error probability at most e provided that |E|<frcase|1/2d|V|2 for some universal constant d<1. 相似文献
4.
Wen-Qing Wang 《Information Processing Letters》2008,107(6):205-210
In this paper, we consider the problem of a fault-free Hamiltonian cycle passing through prescribed edges in an n-dimensional hypercube Qn with some faulty edges. We obtain the following result: Let n?2, F⊂E(Qn), E0⊂E(Qn)\F with 1?|E0|?2n−3, |F|<n−(⌊|E0|/2⌋+1). If the subgraph induced by E0 is a linear forest (i.e., pairwise vertex-disjoint paths), then in the graph Qn−F all edges of E0 lie on a Hamiltonian cycle. 相似文献
5.
Given a graph G=(V,E) and a set of vertices M ? V, a vertex v ∈ V is said to be controlled by M if the majority of v’s neighbors (including itself) belong to M. M is called a monopoly in G if every vertex v∈ V is controlled by M. For a specified M and a given range for edge set E (E 1 ? E ? E 2), we try to determine an E such that M is a monopoly in G=(V,E). We first present a polynomial algorithm for testing if such an E exists, by formulating it as a network flow problem. Assuming that a solution for E does exist, we then show that solutions with the maximum and minimum |E| , respectively, can be found in polynomial time, by solving weighted matching problems. In case there is no solution for E, we want to maximize the number of vertices controlled by the given M. Unfortunately, this problem turns out to be NP-hard. We, therefore, design a simple approximation algorithm which guarantees an approximation ratio of 2. 相似文献
6.
Given a bipartite graph G=(V,W,E) with a bipartition {V,W} of a vertex set and an edge set E, a 2-layered drawing of G in the plane means that the vertices of V and W are respectively drawn as distinct points on two parallel lines and the edges as straight line segments. We consider the problem of counting the number of edge crossings. In this paper, we design two algorithms to this problem based on the dynamic programming and divide-and-conquer approaches. These algorithms run in O(n1n2) time and O(m) space and in O(min{n1n2,|E|log(min{|V|,|W|})}) time and O(m) space, respectively. Our algorithms outperform the previously fastest Θ(|E|log(min{|V|,|W|})) time algorithm for dense graphs. 相似文献
7.
Many hard algorithmic problems dealing with graphs, circuits, formulas and constraints admit polynomial-time upper bounds if the underlying graph has small treewidth. The same problems often encourage reducing the maximal degree of vertices to simplify theoretical arguments or address practical concerns. Such degree reduction can be performed through a sequence of splittings of vertices, resulting in an expansion of the original graph. We observe that the treewidth of a graph may increase dramatically if the splittings are not performed carefully. In this context we address the following natural question: is it possible to reduce the maximum degree to a constant without substantially increasing the treewidth?We answer the above question affirmatively. We prove that any simple undirected graph G=(V,E) admits an expansion G′=(V′,E′) with the maximum degree ≤3 and tw(G′)≤tw(G)+1, where tw(?) is the treewidth of a graph. Furthermore, such an expansion will have no more than 2|E|+|V| vertices and 3|E| edges; it can be computed efficiently from a tree-decomposition of G. We also construct a family of examples for which the increase by 1 in treewidth cannot be avoided. 相似文献
8.
Vladimir Kolmogorov 《Algorithmica》2010,56(4):394-412
We consider the following problem: given an undirected weighted graph G=(V,E,c) with nonnegative weights, minimize function c(δ(Π))−λ|Π| for all values of parameter λ. Here Π is a partition of the set of nodes, the first term is the cost of edges whose endpoints belong to different components
of the partition, and |Π| is the number of components. The current best known algorithm for this problem has complexity O(|V|2) maximum flow computations. We improve it to |V| parametric maximum flow computations. We observe that the complexity can be improved further for families of graphs which admit a good
separator, e.g. for planar graphs. 相似文献
9.
《Journal of Parallel and Distributed Computing》1994,23(3):399-410
Repeated computation of associative functions is central to many asynchronous distributed algorithms reported in the literature. We present efficient distributed algorithms for computing associative functions in spite of undetectable link failures in non-partitioned distributed systems. Two distributed; algorithms are presented for function computation assuming that the distributed system is preprocessed by a one-time preprocessing step that uses O(|E| |V|) messages (where |E| and |V| are the number of links and the number of nodes of the system, respectively). The first algorithm tolerates single link failures using O(|V| log |V|) messages and the second algorithm, which is an extension of the first algorithm, copes with the simultaneous failure of k links using O(k|E| log |V|) messages. Efficient computation of associative functions in the presence of multiple link failures has been an open problem, and our work solves this open problem. 相似文献
10.
《Journal of Parallel and Distributed Computing》2004,64(5):662-685
In this paper, we solve the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs efficiently in parallel. Let Td(|V|,|E|) and Pd(|V|,|E|) denote the parallel time and processor complexities, respectively, required to construct a decomposition tree of a distance-hereditary graph G=(V,E) on a PRAM model Md. We show that this problem can be solved in O(Td(|V|,|E|)+log|V|) time using O(Pd(|V|,|E|)+(|V|+|E|)/log|V|) processors on Md. Moreover, if G is represented by its decomposition tree form, the problem can be solved optimally in O(log|V|) time using O((|V|+|E|)/log|V|) processors on an EREW PRAM. We also obtain a linear-time algorithm which is faster than the previous known O(|V|3) sequential algorithm. 相似文献
11.
《Computers & Operations Research》2005,32(3):571-581
In this paper we consider a traffic-light network where every node in the network is associated with the constraint consisting of a repeated sequence of time windows. The constraint aims to simulate the operations of traffic-light control in an intersection of roads. With this kind of constraints in place, directions of routes when passing through the intersections can be formally modeled. The objective of this paper is to find the first K shortest looping paths in the traffic-light network. An algorithm of time complexity of O(rK2|V1|3) is developed, where r is the number of different windows of a node and |V1| is the number of nodes in the original network. 相似文献
12.
We study the problem of solving simple stochastic games, and give both an interesting new algorithm and a hardness result. We show a reduction from fine approximation of simple stochastic games to coarse approximation of a polynomial sized game, which can be viewed as an evidence showing the hardness to approximate the value of simple stochastic games. We also present a randomized algorithm that runs in \(\tilde{O}(\sqrt{|V_{\mathrm{R}}|!})\) time, where |V R| is the number of RANDOM vertices and \(\tilde{O}\) ignores polynomial terms. This algorithm is the fastest known algorithm when |V R|=ω(log?n) and \(|V_{\mathrm{R}}|=o(\sqrt{\min{|V_{\min}|,|V_{\max}|}})\) and it works for general (non-stopping) simple stochastic games. 相似文献
13.
In communication networks, many applications, such as video on demand and video conferencing, must establish a communications tree that spans a subset K in a vertex set. The source node can then send identical data to all nodes in set K along this tree. This kind of communication is known as multicast communication. A network optimization problem, called the Steiner tree problem (STP), is presented to find a least cost multicasting tree. In this paper, an O(|E|) algorithm is presented to find a minimum Steiner tree for series-parallel graphs where |E| is the number of edges. Based on this algorithm, we proposed an O(22c·|E|) algorithm to solve the Steiner tree problem for general graphs where c is the number of applied factoring procedures. The c value is strongly related to the topology of a given graph. This is quite different from other algorithms with exponential time complexities in |K|. 相似文献
14.
《Computers & chemistry》1990,14(3):225-236
An interdimensional degeneracy linking the orbital angular momentum projection |m| and spatial dimension D yields D-dimensional eigenstates for H2+ by simple correspondence with suitably scaled D = 3 excited states. The wave-equation for fixed nuclei is separable in D-dimensional spheroidal coordinates, giving generalized two-center differential equations with parametric dependence on the internuclear distance R. A computer program is presented which is capable of calculating the two eigenparameters, the energy ED(R), and the separation constant AD(R) related to the total orbital angular momentum and the Runge-Lenz vector, to high accuracy over a large range in R for dimensions up to D = 100, or equivalently, for projections up to |m| = 50 for D = 3. The program can be implemented on personal computers to give accuracies up to 16 digits. The execution times required are modest. Normalization constants, wavefunctions and expectation values can be calculated as well, but at a cost of much larger execution times for even moderate accuracy. 相似文献
15.
Yun-Sheng Chung 《Information Processing Letters》2007,103(6):240-246
Imposing constraints is an effective means to incorporate biological knowledge into alignment procedures. As in the PROSITE database, functional sites of proteins can be effectively described as regular expressions. In an alignment of protein sequences it is natural to expect that functional motifs should be aligned together. Due to this motivation, Arslan introduced the regular expression constrained sequence alignment problem and proposed an algorithm which, if implemented naïvely, can take time and space up to O(2|Σ|4|V|n2) and O(2|Σ|4|V|n), respectively, where Σ is the alphabet, n is the sequence length, and V is the set of states in an automaton equivalent to the input regular expression. In this paper we propose a more efficient algorithm solving this problem which takes O(3|V|n2) time and O(2|V|n) space in the worst case. If |V|=O(logn) we propose another algorithm with time complexity O(2|V|log|V|n2). The time complexity of our algorithms is independent of Σ, which is desirable in protein applications where the formulation of this problem originates; a factor of 2|Σ|=400 in the time complexity of the previously proposed algorithm would significantly affect the efficiency in practice. 相似文献
16.
Finding a path that satisfies multiple Quality-of-Service (QoS) constraints is vital to the deployment of current emerged services. However, existing algorithms are not very efficient and effective at finding such a path. Moreover, few works focus on three or more QoS constraints. In this paper, we present an enhanced version of fully polynomial time approximation scheme (EFPTAS) for multiconstrainted path optimal (MCOP) problem. Specifically, we make four major contributions. We first allow the proposed algorithm to construct an auxiliary graph, through which the QoS parameters on each of the finding path can be guaranteed not to exceed the given constraints. Then we adopt a concept, called nonlinear definition of path constraints in EFPTAS for reducing both time and space complexity. Also, we enable EFPTAS to run iteratively to facilitate a progressive refinement of the finding result. In addition to these, we identify some “deployment” issues for proposed algorithm, the essential steps that how and when the EFPTAS takes place are presented. By analyzing the proposed algorithm theoretically, we find that the presented EFPTAS can find a (1+ε)-approximation path in the network with time complexity O(|E||V|/ε) (where |E| is the number of edges and |V| is the number of nodes), which outperforms the previous best-known algorithm for MCOP. We conduct an extensive comparison between the algorithm presented in this paper and previous best-known study experimentally, our results indicate that EFPTAS can find a path with low complexity and preferable quality. 相似文献
17.
For a graph G=(V,E) and a color set C, let f:E→C be an edge-coloring of G in which two adjacent edges may have the same color. Then, the graph G edge-colored by f is rainbow connected if every two vertices of G have a path in which all edges are assigned distinct colors. Chakraborty et al. defined the problem of determining whether the graph colored by a given edge-coloring is rainbow connected. Chen et al. introduced the vertex-coloring version of the problem as a variant, and we introduce the total-coloring version in this paper. We settle the precise computational complexities of all the three problems with regards to graph diameters, and also characterize these with regards to certain graph classes: cacti, outer planer and series-parallel graphs. We then give FPT algorithms for the three problems on general graphs when parameterized by the number of colors in C; our FPT algorithms imply that all the three problems can be solved in polynomial time for any graph with n vertices if |C|=O(logn). 相似文献
18.
In this paper, we consider the fault hamiltonicity and the fault hamiltonian connectivity of the pancake graph Pn. Assume that F⊆V(Pn)∪E(Pn). For n?4, we prove that Pn−F is hamiltonian if |F|?(n−3) and Pn−F is hamiltonian connected if |F|?(n−4). Moreover, all the bounds are optimal. 相似文献
19.
Katarzyna Jesse-Józefczyk 《Theoretical computer science》2012,414(1):38-46
Let G=(V,E) be a graph. A global secure set SD⊆V is a dominating set which also satisfies a condition that |N[X]∩SD|≥|N[X]−SD| for every subset X⊆SD. The minimum cardinality of the global secure set in the graph G is denoted by γs(G). In this paper, we introduce the notion of γs-monotone graphs. The graph G is γs-monotone if, for every k∈{γs(G),γs(G)+1,…,n}, it has a global secure set of cardinality k. We will also present the results concerning the minimum cardinality of the global secure sets in the class of cographs. 相似文献
20.
Takeaki Uno 《Algorithmica》2010,56(1):3-16
The problem of finding dense structures in a given graph is quite basic in informatics including data mining and data engineering.
Clique is a popular model to represent dense structures, and widely used because of its simplicity and ease in handling. Pseudo
cliques are natural extension of cliques which are subgraphs obtained by removing small number of edges from cliques. We here
define a pseudo clique by a subgraph such that the ratio of the number of its edges compared to that of the clique with the
same number of vertices is no less than a given threshold value. In this paper, we address the problem of enumerating all
pseudo cliques for a given graph and a threshold value. We first show that it seems to be difficult to obtain polynomial time
algorithms using straightforward divide and conquer approaches. Then, we propose a polynomial time, polynomial delay in precise,
algorithm based on reverse search. The time complexity for each pseudo clique is O(Δlog |V|+min {Δ
2,|V|+|E|}). Computational experiments show the efficiency of our algorithm for both randomly generated graphs and practical graphs. 相似文献