共查询到20条相似文献,搜索用时 31 毫秒
1.
We study complexity and approximation of min weighted node coloring in planar, bipartite and split graphs. We show that this problem is NP-hard in planar graphs, even if they are triangle-free and their maximum degree is bounded above by 4. Then, we prove that min weighted node coloring is NP-hard in P8-free bipartite graphs, but polynomial for P5-free bipartite graphs. We next focus on approximability in general bipartite graphs and improve earlier approximation results by giving approximation ratios matching inapproximability bounds. We next deal with min weighted edge coloring in bipartite graphs. We show that this problem remains strongly NP-hard, even in the case where the input graph is both cubic and planar. Furthermore, we provide an inapproximability bound of 7/6−ε, for any ε>0 and we give an approximation algorithm with the same ratio. Finally, we show that min weighted node coloring in split graphs can be solved by a polynomial time approximation scheme. 相似文献
2.
Amotz Bar-Noy Magnús M. Halldrsson Guy Kortsarz Ravit Salman Hadas Shachnai 《Journal of Algorithms in Cognition, Informatics and Logic》2000,37(2):422
Scheduling dependent jobs on multiple machines is modeled by the graph multicoloring problem. In this paper we consider the problem of minimizing the average completion time of all jobs. This is formalized as the sum multicoloring problem: Given a graph and the number of colors required by each vertex, find a multicoloring which minimizes the sum of the largest colors assigned to the vertices. It reduces to the known sum coloring problem when each vertex requires exactly one color.This paper reports a comprehensive study of the sum multicoloring problem, treating three models: with and without preemptions, as well as co-scheduling where jobs cannot start while others are running. We establish a linear relation between the approximability of the maximum independent set problem and the approximability of the sum multicoloring problem in all three models, via a link to the sum coloring problem. Thus, for classes of graphs for which the independent set problem is ρ-approximable, we obtain O(ρ)-approximations for preemptive and co-scheduling sum multicoloring and O(ρ log n)-approximation for nonpreemptive sum multicoloring. In addition, we give constant ratio approximations for a number of fundamental classes of graphs, including bipartite, line, bounded degree, and planar graphs. 相似文献
3.
Yuichi Asahiro 《Discrete Applied Mathematics》2011,159(7):498-508
Given an undirected graph with edge weights, we are asked to find an orientation, that is, an assignment of a direction to each edge, so as to minimize the weighted maximum outdegree in the resulted directed graph. The problem is called MMO, and is a restricted variant of the well-known minimum makespan problem. As in previous studies, it is shown that MMO is in P for trees, weak NP-hard for planar bipartite graphs, and strong NP-hard for general graphs. There are still gaps between those graph classes. The objective of this paper is to show tighter thresholds of complexity: We show that MMO is (i) in P for cactus graphs, (ii) weakly NP-hard for outerplanar graphs, and also (iii) strongly NP-hard for graphs which are both planar and bipartite. This implies the NP-hardness for P4-bipartite, diamond-free or house-free graphs, each of which is a superclass of cactus. We also show (iv) the NP-hardness for series-parallel graphs and multi-outerplanar graphs, and (v) present a pseudo-polynomial time algorithm for graphs with bounded treewidth. 相似文献
4.
On shortest disjoint paths in planar graphs 总被引:1,自引:0,他引:1
For a graph G and a collection of vertex pairs {(s1,t1),…,(sk,tk)}, the k disjoint paths problem is to find k vertex-disjoint paths P1,…,Pk, where Pi is a path from si to ti for each i=1,…,k. In the corresponding optimization problem, the shortest disjoint paths problem, the vertex-disjoint paths Pi have to be chosen such that a given objective function is minimized. We consider two different objectives, namely minimizing the total path length (minimum sum, or short: Min-Sum), and minimizing the length of the longest path (Min-Max), for k=2,3.Min-Sum: We extend recent results by Colin de Verdière and Schrijver to prove that, for a planar graph and for terminals adjacent to at most two faces, the Min-Sum 2 Disjoint Paths Problem can be solved in polynomial time. We also prove that, for six terminals adjacent to one face in any order, the Min-Sum 3 Disjoint Paths Problem can be solved in polynomial time.Min-Max: The Min-Max 2 Disjoint Paths Problem is known to be NP-hard for general graphs. We present an algorithm that solves the problem for graphs with tree-width 2 in polynomial time. We thus close the gap between easy and hard instances, since the problem is weakly NP-hard for graphs with tree-width 3. 相似文献
5.
Mirela Damian-Iordache Sriram V. Pemmaraju 《Journal of Algorithms in Cognition, Informatics and Logic》2002,42(2):255
The main result of this paper is a (2 + )-approximation scheme for the minimum dominating set problem on circle graphs. We first present an O(n2) time 8-approximation algorithm for this problem and then extend it to an
time (2 + )-approximation scheme for this problem. Here n and m are the number of vertices and the number of edges of the circle graph. We then present simple modifications to this algorithm that yield (3 + )-approximation schemes for the minimum connected and the minimum total dominating set problems on circle graphs. Keil (1993, Discrete Appl. Math.42, 51–63) shows that these problems are NP-complete for circle graphs and leaves open the problem of devising approximation algorithms for them. These are the first O(1)-approximation algorithms for domination problems on circle graphs. 相似文献
6.
For a bounded integer ℓ, we wish to color all edges of a graph G so that any two edges within distance ℓ have different colors. Such a coloring is called a distance-edge-coloring or an ℓ-edge-coloring of G. The distance-edge-coloring problem is to compute the minimum number of colors required for a distance-edge-coloring of a given graph G. A partial k-tree is a graph with tree-width bounded by a fixed constant k. We first present a polynomial-time exact algorithm to solve the problem for partial k-trees, and then give a polynomial-time 2-approximation algorithm for planar graphs. 相似文献
7.
Adrian Kosowski 《Discrete Applied Mathematics》2009,157(11):2552-2554
The strength of a graph G is the smallest integer s such that there exists a minimum sum coloring of G using integers {1,…,s}, only. For bipartite graphs of maximum degree Δ we show the following simple bound: s≤⌈Δ/2⌉+1. As a consequence, there exists a quadratic time algorithm for determining the strength and minimum color sum of bipartite graphs of maximum degree Δ≤4. 相似文献
8.
Heike Sperber 《Mathematical Methods of Operations Research》2010,71(2):245-265
We study the complexity of finding extreme pure Nash equilibria in symmetric network congestion games and analyse how it is
influenced by the graph topology and the number of users. In our context best and worst equilibria are those with minimum
or maximum total latency, respectively. We establish that both problems can be solved by a Greedy type algorithm equipped
with a suitable tie breaking rule on extension-parallel graphs. On series-parallel graphs finding a worst Nash equilibrium
is NP-hard for two or more users while finding a best one is solvable in polynomial time for two users and NP-hard for three or more. additionally we establish NP-hardness in the strong sense for the problem of finding a worst Nash equilibrium on a general acyclic graph. 相似文献
9.
In this paper, we study the minimum sum coloring (MSC) problem on P 4-sparse graphs. In the MSC problem, we aim to assign natural numbers to vertices of a graph such that adjacent vertices get different numbers, and the sum of the numbers assigned to the vertices is minimum. Based in the concept of maximal sequence associated with an optimal solution of the MSC problem of any graph, we show that there is a large sub-family of P 4-sparse graphs for which the MSC problem can be solved in polynomial time. Moreover, we give a parameterized algorithm and a 2-approximation algorithm for the MSC problem on general P 4-sparse graphs. 相似文献
10.
Polar graphs generalise bipartite graphs, cobipartite graphs, and split graphs, and they constitute a special type of matrix partitions. A graph is polar if its vertex set can be partitioned into two, such that one part induces a complete multipartite graph and the other part induces a disjoint union of complete graphs. Deciding whether a given arbitrary graph is polar, is an NP-complete problem. Here, we show that for permutation graphs this problem can be solved in polynomial time. The result is surprising, as related problems like achromatic number and cochromatic number are NP-complete on permutation graphs. We give a polynomial-time algorithm for recognising graphs that are both permutation and polar. Prior to our result, polarity has been resolved only for chordal graphs and cographs. 相似文献
11.
Paul D. Manuel Mostafa I. Abd-El-Barr Indra Rajasingh Bharati Rajan 《Journal of Discrete Algorithms》2008,6(1):11-19
The most popular bounded-degree derivative network of the hypercube is the butterfly network. The Benes network consists of back-to-back butterflies. There exist a number of topological representations that are used to describe butterfly—like architectures. We identify a new topological representation of butterfly and Benes networks.The minimum metric dimension problem is to find a minimum set of vertices of a graph G(V,E) such that for every pair of vertices u and v of G, there exists a vertex w with the condition that the length of a shortest path from u to w is different from the length of a shortest path from v to w. It is NP-hard in the general sense. We show that it remains NP-hard for bipartite graphs. The algorithmic complexity status of this NP-hard problem is not known for butterfly and Benes networks, which are subclasses of bipartite graphs. By using the proposed new representations, we solve the minimum metric dimension problem for butterfly and Benes networks. The minimum metric dimension problem is important in areas such as robot navigation in space applications. 相似文献
12.
Let G be an edge-colored graph. The monochromatic tree partition problem is to find the minimum number of vertex disjoint monochromatic
trees to cover the all vertices of G. In the authors’ previous work, it has been proved that the problem is NP-complete and there does not exist any constant
factor approximation algorithm for it unless P = NP. In this paper the authors show that for any fixed integer r ≥ 5, if the edges of a graph G are colored by r colors, called an r-edge-colored graph, the problem remains NP-complete. Similar result holds for the monochromatic path (cycle) partition problem.
Therefore, to find some classes of interesting graphs for which the problem can be solved in polynomial time seems interesting.
A linear time algorithm for the monochromatic path partition problem for edge-colored trees is given.
Supported by the National Natural Science Foundation of China, PCSIRT and the “973” Program. 相似文献
13.
Fahimeh Baroughi Bonab Rainer E. Burkard Elisabeth Gassner 《Mathematical Methods of Operations Research》2011,73(2):263-280
The inverse p-median problem with variable edge lengths on graphs is to modify the edge lengths at minimum total cost with respect to given
modification bounds such that a prespecified set of p vertices becomes a p-median with respect to the new edge lengths. The problem is shown to be strongly NP{\mathcal{NP}}-hard on general graphs and weakly NP{\mathcal{NP}}-hard on series-parallel graphs. Therefore, the special case on a tree is considered: It is shown that the inverse 2-median
problem with variable edge lengths on trees is solvable in polynomial time. For the special case of a star graph we suggest
a linear time algorithm. 相似文献
14.
Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane 总被引:1,自引:0,他引:1
Hiroshi Imai Takao Asano 《Journal of Algorithms in Cognition, Informatics and Logic》1983,4(4):310-323
An intersection graph of rectangles in the (x, y)-plane with sides parallel to the axes is obtained by representing each rectangle by a vertex and connecting two vertices by an edge if and only if the corresponding rectangles intersect. This paper describes algorithms for two problems on intersection graphs of rectangles in the plane. One is an O(n log n) algorithm for finding the connected components of an intersection graph of n rectangles. This algorithm is optimal to within a constant factor. The other is an O(n log n) algorithm for finding a maximum clique of such a graph. It seems interesting that the maximum clique problem is polynomially solvable, because other related problems, such as the maximum stable set problem and the minimum clique cover problem, are known to be NP-complete for intersection graphs of rectangles. Furthermore, we briefly show that the k-colorability problem on intersection graphs of rectangles is NP-complete. 相似文献
15.
Given a simple undirected graph, the minimum connected dominating set problem is to find a minimum cardinality subset of vertices
D inducing a connected subgraph such that each vertex outside D has at least one neighbor in D. Approximations of minimum connected dominating sets are often used to represent a virtual routing backbone in wireless networks. This paper first proposes a constant-ratio approximation algorithm for the minimum connected dominating
set problem in unit ball graphs and then introduces and studies the edge-weighted bottleneck connected dominating set problem,
which seeks a minimum edge weight in the graph such that the corresponding bottleneck subgraph has a connected dominating
set of size k. In wireless network applications this problem can be used to determine an optimal transmission range for a network with
a predefined size of the virtual backbone. We show that the problem is hard to approximate within a factor better than 2 in
graphs whose edge weights satisfy the triangle inequality and provide a 3-approximation algorithm for such graphs. We also
show that for fixed k the problem is polynomially solvable in unit disk and unit ball graphs. 相似文献
16.
Path problems such as the maximum edge-disjoint paths problem, the path coloring problem, and the maximum path coloring problem are relevant for resource allocation in communication networks, in particular all-optical networks. In this paper, it is shown that maximum path coloring can be solved optimally in polynomial time for bidirected generalized stars, even in the weighted case. Furthermore, the maximum edge-disjoint paths problem is proved NP-hard for complete graphs (undirected or bidirected), a constant-factor off-line approximation algorithm is presented for the weighted case, and an on-line algorithm with constant competitive ratio is given for the unweighted case. Finally, an open problem concerning the existence of routings that simultaneously minimize the maximum load and the number of colors is solved: an example for a graph and a set of requests is given such that any routing that minimizes the maximum load requires strictly more colors for path coloring than a routing that minimizes the number of colors. 相似文献
17.
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. 相似文献
18.
Refael Hassin Samir Khuller 《Journal of Algorithms in Cognition, Informatics and Logic》2001,41(2):429
Approximation algorithms for NP-hard optimization problems have been widely studied for over three decades. Most of these measure the quality of the solution produced by taking the ratio of the cost of the solution produced by the algorithm to the cost of an optimal solution. In certain cases, this ratio may not be very meaningful—for example, if the ratio of the worst solution to the best solution is at most some constant α, then an approximation algorithm with factor α may in fact yield the worst solution! To overcome this hurdle (among others), several authors have independently suggested the use of a different measure which we call z-approximation. An algorithm is an α z-approximation if it runs in polynomial time and produces a solution whose distance from the optimal one is at most α times the distance between the optimal solution and the worst possible solution. The results known so far about z-approximations are either of the inapproximability type or rather straightforward observations. We design polynomial time algorithms for several fundamental discrete optimization problems; in particular we obtain a z-approximation factor of
for the
(TSP) (with no triangle inequality assumption). For the
TSP this improves to
. We also show that if there is a polynomial time algorithm that for any fixed ε > 0 yields an ε z-approximation then P = NP. We also present z-approximations for severa1 other problems such as
, and
. 相似文献
Full-size image
Full-size image
Full-size image
19.
Given graphs G, H, and lists L(v) ? V(H), v ε V(G), a list homomorphism of G to H with respect to the lists L is a mapping f : V(G) → V(H) such that uv ε E(G) implies f(u)f(v) ε E(H), and f(v) ε L(v) for all v ε V(G). The list homomorphism problem for a fixed graph H asks whether or not an input graph G, together with lists L(v) ? V(H), v ε V(G), admits a list homomorphism with respect to L. In two earlier papers, we classified the complexity of the list homomorphism problem in two important special cases: When H is a reflexive graph (every vertex has a loop), the problem is polynomial time solvable if H is an interval graph, and is NP‐complete otherwise. When H is an irreflexive graph (no vertex has a loop), the problem is polynomial time solvable if H is bipartite and H is a circular arc graph, and is NP‐complete otherwise. In this paper, we extend these classifications to arbitrary graphs H (each vertex may or may not have a loop). We introduce a new class of graphs, called bi‐arc graphs, which contains both reflexive interval graphs (and no other reflexive graphs), and bipartite graphs with circular arc complements (and no other irreflexive graphs). We show that the problem is polynomial time solvable when H is a bi‐arc graph, and is NP‐complete otherwise. In the case when H is a tree (with loops allowed), we give a simpler algorithm based on a structural characterization. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 61–80, 2003 相似文献
20.
The bipartite density of a graph G is max {|E(H)|/|E(G)|: H is a bipartite subgraph of G}. It is NP-hard to determine the bipartite density of any triangle-free cubic graph. A biased maximum bipartite subgraph of a graph G is a bipartite subgraph of G with the maximum number of edges such that one of its partite sets is independent in G. Let $
\mathcal{H}
$
\mathcal{H}
denote the collection of all connected cubic graphs which have bipartite density $
\tfrac{4}
{5}
$
\tfrac{4}
{5}
and contain biased maximum bipartite subgraphs. Bollobás and Scott asked which cubic graphs belong to $
\mathcal{H}
$
\mathcal{H}
. This same problem was also proposed by Malle in 1982. We show that any graph in $
\mathcal{H}
$
\mathcal{H}
can be reduced, through a sequence of three types of operations, to a member of a well characterized class. As a consequence,
we give an algorithm that decides whether a given graph G belongs to $
\mathcal{H}
$
\mathcal{H}
. Our algorithm runs in polynomial time, provided that G has a constant number of triangles that are not blocks of G and do not share edges with any other triangles in G. 相似文献