共查询到20条相似文献,搜索用时 25 毫秒
1.
Given a directed graph G=(N,A) with arc capacities u
ij
and a minimum cost flow problem defined on G, the capacity inverse minimum cost flow problem is to find a new capacity vector
[^(u)]\hat{u}
for the arc set A such that a given feasible flow
[^(x)]\hat{x}
is optimal with respect to the modified capacities. Among all capacity vectors
[^(u)]\hat{u}
satisfying this condition, we would like to find one with minimum
||[^(u)]-u||\|\hat{u}-u\|
value.
We consider two distance measures for
||[^(u)]-u||\|\hat{u}-u\|
, rectilinear (L
1) and Chebyshev (L
∞) distances. By reduction from the feedback arc set problem we show that the capacity inverse minimum cost flow problem is
NP\mathcal{NP}
-hard in the rectilinear case. On the other hand, it is polynomially solvable by a greedy algorithm for the Chebyshev norm.
In the latter case we propose a heuristic for the bicriteria problem, where we minimize among all optimal solutions the number
of affected arcs. We also present computational results for this heuristic. 相似文献
2.
Bang Ye Wu 《Journal of Combinatorial Optimization》2013,26(3):592-607
For given a pair of nodes in a graph, the minimum non-separating path problem looks for a minimum weight path between the two nodes such that the remaining graph after removing the path is still connected. The balanced connected bipartition (BCP2) problem looks for a way to bipartition a graph into two connected subgraphs with their weights as equal as possible. In this paper we present an algorithm in time O(NlogN) for finding a minimum weight non-separating path between two given nodes in a grid graph of N nodes with positive weight. This result leads to a 5/4-approximation algorithm for the BCP2 problem on grid graphs, which is the currently best ratio achieved in polynomial time. We also developed an exact algorithm for the BCP2 problem on grid graphs. Based on the exact algorithm and a rounding technique, we show an approximation scheme, which is a fully polynomial time approximation scheme for fixed number of rows. 相似文献
3.
This paper solves the problem of increasing the edge-connectivity of a bipartite digraph by adding the smallest number of new edges that preserve bipartiteness. A natural application arises when we wish to reinforce a 2-dimensional square grid framework with cables. We actually solve the more general problem of covering a crossing family of sets with the smallest number of directed edges, where each new edge must join the blocks of a given bipartition of the elements. The smallest number of new edges is given by a min-max formula that has six infinite families of exceptional cases. We discuss a problem on network flows whose solution has a similar formula with three infinite families of exceptional cases. We also discuss a problem on arborescences whose solution has five infinite families of exceptions. We give an algorithm that increases the edge-connectivity of a bipartite digraph in the same time as the best-known algorithm for the problem without the bipartite constraint: O(km log n) for unweighted digraphs and O(nm log (n
2/m)) for weighted digraphs, where n, m and k are the number of vertices and edges of the given graph and the target connectivity, respectively. 相似文献
4.
Markus Behle 《Journal of Combinatorial Optimization》2008,16(2):107-118
Many combinatorial optimization problems can be formulated as 0/1 integer programs (0/1 IPs). The investigation of the structure
of these problems raises the following tasks: count or enumerate the feasible solutions and find an optimal solution according
to a given linear objective function. All these tasks can be accomplished using binary decision diagrams (BDDs), a very popular
and effective datastructure in computational logics and hardware verification.
We present a novel approach for these tasks which consists of an output-sensitive algorithm for building a BDD for a linear constraint (a so-called threshold BDD) and a parallel AND operation on threshold BDDs. In particular our algorithm is capable of solving knapsack problems, subset sum problems
and multidimensional knapsack problems.
BDDs are represented as a directed acyclic graph. The size of a BDD is the number of nodes of its graph. It heavily depends
on the chosen variable ordering. Finding the optimal variable ordering is an NP-hard problem. We derive a 0/1 IP for finding
an optimal variable ordering of a threshold BDD. This 0/1 IP formulation provides the basis for the computation of the variable
ordering spectrum of a threshold function.
We introduce our new tool azove 2.0 as an enhancement to azove 1.1 which is a tool for counting and enumerating 0/1 points. Computational results on benchmarks from the literature show the
strength of our new method. 相似文献
5.
The problem of partitioning a partially ordered set into a minimum number of chains is a well-known problem. In this paper
we study a generalization of this problem, where we not only assume that the chains have bounded size, but also that a weight
w
i
is given for each element i in the partial order such that w
i
≤w
j
if i
≺
j. The problem is then to partition the partial order into a minimum-weight set of chains of bounded size, where the weight
of a chain equals the weight of the heaviest element in the chain. We prove that this problem is
-hard, and we propose and analyze lower bounds for this problem. Based on these lower bounds, we exhibit a 2-approximation
algorithm, and show that it is tight. We report computational results for a number of real-world and randomly generated problem
instances. 相似文献
6.
William S. Kennedy Hui Kong Guohui Lin Guiying Yan 《Journal of Combinatorial Optimization》2010,19(1):94-106
Inspired by phylogenetic tree construction in computational biology, Lin et al. (The 11th Annual International Symposium on
Algorithms and Computation (ISAAC 2000), pp. 539–551, 2000) introduced the notion of a k
-phylogenetic root. A k-phylogenetic root of a graph G is a tree T such that the leaves of T are the vertices of G, two vertices are adjacent in G precisely if they are within distance k in T, and all non-leaf vertices of T have degree at least three. The k-phylogenetic root problem is to decide whether such a tree T exists for a given graph G. In addition to introducing this problem, Lin et al. designed linear time constructive algorithms for k≤4, while left the problem open for k≥5. In this paper, we partially fill this hole by giving a linear time constructive algorithm to decide whether a given tree
chordal graph has a 5-phylogenetic root; this is the largest class of graphs known to have such a construction. 相似文献
7.
A graph \(G=(V,E)\) with even number vertices is called Pfaffian if it has a Pfaffian orientation, namely it admits an orientation such that the number of edges of any M-alternating cycle which have the same direction as the traversal direction is odd for some perfect matching M of the graph G. In this paper, we obtain a necessary and sufficient condition of Pfaffian graphs in a type of bipartite graphs. Then, we design an \(O(|E(G)|^2)\) algorithm for recognizing Pfaffian graphs in this class and constructs a Pfaffian orientation if the graph is Pfaffian. The results improve and generalize some known results. 相似文献
8.
Peter Damaschke 《Journal of Combinatorial Optimization》2009,18(3):294-306
The multiple weighted hitting set problem is to find a subset of nodes in a hypergraph that hits every hyperedge in at least
m nodes. We extend the problem to a notion of hypergraphs with so-called hypernodes and show that, for m=2, it remains fixed-parameter tractable (FPT), parameterized by the number of hyperedges. This is accomplished by a nontrivial
extension of the dynamic programming algorithm for hypergraphs. The algorithm might be interesting for certain assignment
problems, but here we need it as a tool to solve another problem motivated by network analysis: A d-core of a graph is a subgraph in which every vertex has at least d neighbors. We give an FPT algorithm that computes a smallest 2-core including a given set of target vertices, where the number
of targets is the parameter. This FPT result is best possible in the sense that no FPT algorithm for 3-cores can be expected. 相似文献
9.
We study minimizing communication cost in parallel algorithm design, by minimizing the number of communication phases in coarse-grained parallel computers. There have been several recent papers dealing with parallel algorithms of small communication cost under different models. Most of these results are for computational geometry problems. For these problems it has been possible to decompose tasks into appropriate subproblems in a communication-efficient way. It appears to be somewhat more difficult to design parallel algorithms with small communication phases for graph theory problems. In this paper we focus on the design of deterministic algorithms with a small number of communication phases for the list ranking problem and the shortest path problem. 相似文献
10.
Mathieu Bouchard Alain Hertz Guy Desaulniers 《Journal of Combinatorial Optimization》2009,17(2):168-191
An edge coloring of a graph G=(V,E) is a function c:E→ℕ that assigns a color c(e) to each edge e∈E such that c(e)≠c(e′) whenever e and e′ have a common endpoint. Denoting S
v
(G,c) the set of colors assigned to the edges incident to a vertex v∈V, and D
v
(G,c) the minimum number of integers which must be added to S
v
(G,c) to form an interval, the deficiency D(G,c) of an edge coloring c is defined as the sum ∑
v∈V
D
v
(G,c), and the span of c is the number of colors used in c. The problem of finding, for a given graph, an edge coloring with a minimum deficiency is NP-hard. We give new lower bounds
on the minimum deficiency of an edge coloring and on the span of edge colorings with minimum deficiency. We also propose a
tabu search algorithm to solve the minimum deficiency problem and report experiments on various graph instances, some of them
having a known optimal deficiency. 相似文献
11.
A fast exact algorithm for the problem of optimum cooperation and the structure of its solutions 总被引:1,自引:1,他引:0
Given a graph G=(V,E) with edge weights w
e
∈ℝ, the optimum cooperation problem consists in determining a partition of the graph that maximizes the sum of weights of
the edges with nodes in the same class plus the number of the classes of the partition. The problem is also known in the literature
as the optimum attack problem in networks. Furthermore, a relevant physics application exists. 相似文献
12.
Maria Liazi Ioannis Milis Fanny Pascual Vassilis Zissimopoulos 《Journal of Combinatorial Optimization》2007,14(4):465-474
The Densest k-Subgraph (DkS) problem asks for a k-vertex subgraph of a given graph with the maximum number of edges. The problem is strongly NP-hard, as a generalization of
the well known Clique problem and we also know that it does not admit a Polynomial Time Approximation Scheme (PTAS). In this paper we focus on
special cases of the problem, with respect to the class of the input graph. Especially, towards the elucidation of the open
questions concerning the complexity of the problem for interval graphs as well as its approximability for chordal graphs,
we consider graphs having special clique graphs. We present a PTAS for stars of cliques and a dynamic programming algorithm
for trees of cliques.
M.L. is co-financed within Op. Education by the ESF (European Social Fund) and National Resources.
V.Z. is partially supported by the Special Research Grants Account of the University of Athens under Grant 70/4/5821. 相似文献
13.
Djangir A. Babayev George I. Bell Urfat G. Nuriyev 《Journal of Combinatorial Optimization》2009,18(2):151-172
A combinatorial optimization problem, called the Bandpass Problem, is introduced. Given a rectangular matrix A of binary elements {0,1} and a positive integer B called the Bandpass Number, a set of B consecutive non-zero elements in any column is called a Bandpass. No two bandpasses in the same column can have common rows.
The Bandpass problem consists of finding an optimal permutation of rows of the matrix, which produces the maximum total number
of bandpasses having the same given bandpass number in all columns.
This combinatorial problem arises in considering the optimal packing of information flows on different wavelengths into groups
to obtain the highest available cost reduction in design and operating the optical communication networks using wavelength
division multiplexing technology. Integer programming models of two versions of the bandpass problems are developed. For a
matrix A with three or more columns the Bandpass problem is proved to be NP-hard. For matrices with two or one column a polynomial
algorithm solving the problem to optimality is presented. For the general case fast performing heuristic polynomial algorithms
are presented, which provide near optimal solutions, acceptable for applications. High quality of the generated heuristic
solutions has been confirmed in the extensive computational experiments.
As an NP-hard combinatorial optimization problem with important applications the Bandpass problem offers a challenge for researchers
to develop efficient computational solution methods. To encourage the further research a Library of Bandpass Problems has
been developed. The Library is open to public and consists of 90 problems of different sizes (numbers of rows, columns and
density of non-zero elements of matrix A and bandpass number B), half of them with known optimal solutions and the second half, without. 相似文献
14.
This paper deals with facility location problems on graphs with positive and negative vertex weights. We consider two different
objective functions: In the first one (MWD) vertices with positive weight are assigned to the closest facility, whereas vertices
with negative weight are assigned to the farthest facility. In the second one (WMD) all the vertices are assigned to the nearest
facility. For the MWD model it is shown that there exists a finite set of points in the graph which contains the locations
of facilities in an optimal solution. Furthermore, algorithms for both models for the 2-median problem on a cycle are developed.
The algorithm for the MWD model runs in linear time, whereas the algorithm for the WMD model has a time complexity of
O(n2)\mathcal{O}(n^{2})
. 相似文献
15.
In this paper, we study the circular packing problem. Its objective is to pack a set of n circular pieces into a rectangular plate R of fixed dimensions L×W. Each piece’s type i, i=1,…,m, is characterized by its radius r
i
and its demand b
i
. The objective is to determine the packing pattern corresponding to the minimum unused area of R for the circular pieces placed. This problem is solved by using a hybrid algorithm that adopts beam search and a looking-ahead
strategy. A node at a level ℓ of the beam-search tree contains a partial solution corresponding to the circles already placed inside R. Each node is then evaluated using a looking-ahead strategy, based on the minimum local-distance heuristic, by computing
the corresponding complete solution. The nodes leading to the best solutions at level ℓ are then chosen for branching. A multi-start strategy is also considered in order to diversify the search space. The computational
results show, on a set of benchmark instances, the effectiveness of the proposed algorithm. 相似文献
16.
17.
Shuo Zhang Xiaofeng Gao Weili Wu Jianzhong Li Hong Gao 《Journal of Combinatorial Optimization》2011,21(2):159-191
We study the problem of processing supergraph queries on graph databases. A graph database D is a large set of graphs. A supergraph query
q on D is to retrieve all the graphs in D such that q is a supergraph of them. The large number of graphs in databases and the NP-completeness of subgraph isomorphism testing
make it challenging to efficiently processing supergraph queries. In this paper, a new approach to processing supergraph queries
is proposed. Specifically, a method for compactly organizing graph databases is first presented. Common subgraphs of the graphs
in a database are stored only once in the compact organization of the database, in order to reduce the overall cost of subgraph
isomorphism testings from the stored graphs to queries during query processing. Then, an exact algorithm and an approximate
algorithm for generating the significant feature set with optimal order are proposed, followed by the algorithms for indices
construction on graph databases. The optimal order on the feature set is to reduce the number of subgraph isomorphism testings
during query processing. Based on the compact organization of graph databases, a novel algorithm for testing subgraph isomorphisms
from multiple graphs to one graph is presented. Finally, based on all the above techniques, a query processing method is proposed.
Analytical and experimental results show that the proposed algorithms outperform the existing similar algorithms by one to
two orders of magnitude. 相似文献
18.
Xiaotie Deng Evangelos Milios Andranik Mirzaian 《Journal of Combinatorial Optimization》2001,5(4):383-395
In the map verification problem, a robot is given a (possibly incorrect) map M of the world G with its position and orientation indicated on the map. The task is to find out whether this map, for the given robot position and its orientation in the map, is correct for the world G. We consider the world model of a graph G = (V
G, E
G) in which, for each vertex, edges incident to the vertex are ordered cyclically around that vertex. (This also holds for the map M = (V
M, E
M.) The robot can traverse edges and enumerate edges incident on the current vertex, but it cannot distinguish vertices (and edges) from each other. To solve the verification problem, the robot uses a portable edge marker, that it can put down at an edge of the graph world G and pick up later as needed. The robot can recognize the edge marker when it encounters it in the world G. By reducing the verification problem to an exploration problem, verification can be completed in O(|V
G| × |E
G|) edge traversals (the mechanical cost) with the help of a single vertex marker which can be dropped and picked up at vertices of the graph world (G. Dudek, M. Jenkin, E. Milios, and D. Wilkes, IEEE Trans. on Robotics and Automation, vol. 7, pp. 859–865, 1991; Robotics and Autonomous Systems, vol. 22(2), pp. 159–178, 1997). In this paper, we show a strategy that verifies a map in O(|V
M|) edge traversals only, using a single edge marker, when M is a plane embedded graph, even though G may not be planar (e.g., G may contain overpasses, tunnels, etc.). 相似文献
19.
Hovhannes A. Harutyunyan Edward Maraachlian 《Journal of Combinatorial Optimization》2008,16(3):307-322
Broadcasting is an information dissemination problem in a connected network, in which one node, called the originator, disseminates a message to all other nodes by placing a series of calls along the communication lines of the network. Finding
the broadcast time of a vertex in an arbitrary graph is NP-complete. The polynomial time solvability is shown only for trees.
In this paper we present a linear algorithm that determines the broadcast time of any originator in an arbitrary unicyclic
graph. As a byproduct, we find a broadcast center of the unicyclic graph. We also present an O(|V|+k
2) algorithm to find the broadcast time of an arbitrary unicyclic graph, where k is the length of the cycle. In the last section we give tight lower and upper bounds on broadcast time of a spanning tree
based on the broadcast time of the unicyclic graph.
The results of Sects. 2, 3 and most of the proofs in Sects. 2, 3 of this paper are presented by Harutyunyan and Maraachlian
(Proceedings of 13th annual COCOON, pp. 372–383, 2007). All results in Sects. 4, 5 and the complete proof of Theorem 3 are new results. 相似文献
20.
A discrete location problem is formulated for the design of a postal service network. The cost objective of this problem includes a nonlinear concave component. A parametric integer programming algorithm is developed to find an approximate solution to the problem. The algorithm reduces the problem into a sequence of p-median problems and deals with the nonlinear cost by a node-replacement scheme. Preliminary computational results are presented. 相似文献