共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
Michel Barbeau Prosenjit Bose Paz Carmi Mathieu Couture Evangelos Kranakis 《Algorithmica》2011,60(2):236-249
We present the first location-oblivious distributed unit disk graph coloring algorithm having a provable performance ratio
of three (i.e. the number of colors used by the algorithm is at most three times the chromatic number of the graph). This
is an improvement over the standard sequential coloring algorithm that has a worst case lower bound on its performance ratio
of 4−3/k (for any k>2, where k is the chromatic number of the unit disk graph achieving the lower bound) (Tsai et al., in Inf. Process. Lett. 84(4):195–199,
2002). We present a slightly better worst case lower bound on the performance ratio of the sequential coloring algorithm for unit
disk graphs with chromatic number 4. Using simulation, we compare our algorithm with other existing unit disk graph coloring
algorithms. 相似文献
3.
For a fixed integer r≥2, the K
r
-packing problem is to find the maximum number of pairwise vertex-disjointK
r
's (complete graphs on r vertices) in a given graph. The K
r
-factor problem asks for the existence of a partition of the vertex set of a graph into K
r
's. The K
r
-packing problem is a natural generalization of the classical matching problem, but turns out to be much harder for r≥3 – it is known that for r≥3 the K
r
-factor problem is NP-complete for graphs with clique number r [16]. This paper considers the complexity of the K
r
-packing problem on restricted classes of graphs.
We first prove that for r≥3 the K
r
-packing problem is NP-complete even when restrict to chordal graphs, planar graphs (for r=3, 4 only), line graphs and total graphs. The hardness result for K
3-packing on chordal graphs answers an open question raised in [6]. We also give (simple) polynomial algorithms for the K
3-packing and the K
r
-factor problems on split graphs (this is interesting in light of the fact that K
r
-packing becomes NP-complete on split graphs for r≥4), and for the K
r
-packing problem on cographs.
Received September 27, 1999; revised August 14, 2000 相似文献
4.
We show efficient algorithms for edge-coloring planar graphs. Our main result is a linear-time algorithm for coloring planar
graphs with maximum degree Δ with max {Δ,9} colors. Thus the coloring is optimal for graphs with maximum degree Δ≥9. Moreover for Δ=4,5,6 we give linear-time algorithms that use Δ+2 colors. These results improve over the algorithms of Chrobak and Yung (J. Algorithms 10:35–51, 1989) and of Chrobak and Nishizeki (J. Algorithms 11:102–116, 1990) which color planar graphs using max {Δ,19} colors in linear time or using max {Δ,9} colors in
time.
R. Cole supported in part by NSF grants CCR0105678 and CCF0515127 and IDM0414763.
Ł. Kowalik supported in part by KBN grant 4T11C04425. Part of this work was done while Ł. Kowalik was staying at the Max Planck
Institute in Saarbruecken, Germany. 相似文献
5.
In the Π-Cluster Editing problem, one is given an undirected graph G, a density measure Π, and an integer k≥0, and needs to decide whether it is possible to transform G by editing (deleting and inserting) at most k edges into a dense cluster graph. Herein, a dense cluster graph is a graph in which every connected component K=(V
K
,E
K
) satisfies Π. The well-studied Cluster Editing problem is a special case of this problem with Π:=“being a clique”. In this work, we consider three other density measures
that generalize cliques: (1) having at most s missing edges (s-defective cliques), (2) having average degree at least |V
K
|−s (average-s-plexes), and (3) having average degree at least μ⋅(|V
K
|−1) (μ-cliques), where s and μ are a fixed integer and a fixed rational number, respectively. We first show that the Π-Cluster Editing problem is NP-complete for all three density measures. Then, we study the fixed-parameter tractability of the three clustering
problems, showing that the first two problems are fixed-parameter tractable with respect to the parameter (s,k) and that the third problem is W[1]-hard with respect to the parameter k for 0<μ<1. 相似文献
6.
Torsten Tholey 《Theory of Computing Systems》2006,39(1):51-78
Given four distinct vertices s1,s2,t1, and t2 of a graph G, the
2-disjoint paths problem is to determine two disjoint paths, p1 from s1 to t1 and p2 from s2 to t2, if such paths exist. Disjoint can mean vertex- or edge-disjoint. Both, the edge- and the vertex-disjoint version of the
problem, are NP-hard in the case of directed graphs.
For undirected graphs, we show that the
O(mn)-time algorithm of Shiloach
can be modified to solve
the 2-vertex-disjoint paths problem
in only O(n + mα(m,n)) time,
where m is the number of edges in G, n is the number
of vertices in G, and where α denotes the inverse of
the Ackermann function. Our result also improves the
running time for the 2-edge-disjoint paths problem on
undirected graphs as well as the running
times for the 2-vertex- and the 2-edge-disjoint paths problem on dags. 相似文献
7.
We introduce a new generalization of the on-line coloring game. We define the concept of bounded family for on-line t-relaxed colorings. This extends the concept of on-line competitive coloring algorithms to t-relaxed colorings. We characterize the trees T for which the family of T-free graphs is bounded and show that the corresponding bounding function is linear. 相似文献
8.
We show that the Dominating Set problem parameterized by solution size is fixed-parameter tractable (FPT) in graphs that do not contain the claw (K1,3, the complete bipartite graph on four vertices where the two parts have one and three vertices, respectively) as an induced subgraph. We present an algorithm that uses 2O(k2)nO(1) time and polynomial space to decide whether a claw-free graph on n vertices has a dominating set of size at most k. Note that this parameterization of Dominating Set is W[2]-hard on the set of all graphs, and thus is unlikely to have an FPT algorithm for graphs in general.The most general class of graphs for which an FPT algorithm was previously known for this parameterization of Dominating Set is the class of Ki,j-free graphs, which exclude, for some fixed i,j∈N, the complete bipartite graph Ki,j as a subgraph. For i,j≥2, the class of claw-free graphs and any class of Ki,j-free graphs are not comparable with respect to set inclusion. We thus extend the range of graphs over which this parameterization of Dominating Set is known to be fixed-parameter tractable.We also show that, in some sense, it is the presence of the claw that makes this parameterization of the Dominating Set problem hard. More precisely, we show that for any t≥4, the Dominating Set problem parameterized by the solution size is W[2]-hard in graphs that exclude the t-claw K1,t as an induced subgraph. Our arguments also imply that the related Connected Dominating Set and Dominating Clique problems are W[2]-hard in these graph classes.Finally, we show that for any t∈N, the Clique problem parameterized by solution size, which is W[1]-hard on general graphs, is FPT in t-claw-free graphs. Our results add to the small and growing collection of FPT results for graph classes defined by excluded subgraphs, rather than by excluded minors. 相似文献
9.
Coloring a k-colorable graph using k colors (k≥3) is a notoriously hard problem. Considering average case analysis allows for better results. In this work we consider the
uniform distribution over k-colorable graphs with n vertices and exactly cn edges, c greater than some sufficiently large constant. We rigorously show that all proper k-colorings of most such graphs lie in a single “cluster”, and agree on all but a small, though constant, portion of the vertices.
We also describe a polynomial time algorithm that whp finds a proper k-coloring of such a random k-colorable graph, thus asserting that most such graphs are easy to color. This should be contrasted with the setting of very
sparse random graphs (which are k-colorable whp), where experimental results show some regime of edge density to be difficult for many coloring heuristics. 相似文献
10.
Leonid Khachiyan Endre Boros Konrad Borys Khaled Elbassioni Vladimir Gurvich Gabor Rudolf Jihui Zhao 《Theory of Computing Systems》2008,43(2):204-233
Given a directed graph G=(V,A) with a non-negative weight (length) function on its arcs w:A→ℝ+ and two terminals s,t∈V, our goal is to destroy all short directed paths from s to t in G by eliminating some arcs of A. This is known as the short paths interdiction problem. We consider several versions of it, and in each case analyze two subcases: total limited interdiction, when a fixed number k of arcs can be removed, and node-wise limited interdiction, when for each node v∈V a fixed number k(v) of out-going arcs can be removed. Our results indicate that the latter subcase is always easier than the former one. In
particular, we show that the short paths node-wise interdiction problem can be efficiently solved by an extension of Dijkstra’s
algorithm. In contrast, the short paths total interdiction problem is known to be NP-hard. We strengthen this hardness result
by deriving the following inapproximability bounds: Given k, it is NP-hard to approximate within a factor c<2 the maximum s–t distance d(s,t) obtainable by removing (at most) k arcs from G. Furthermore, given d, it is NP-hard to approximate within a factor
the minimum number of arcs which has to be removed to guarantee d(s,t)≥d. Finally, we also show that the same inapproximability bounds hold for undirected graphs and/or node elimination.
This research was supported in part by NSF grant IIS-0118635 and by DIMACS, the NSF Center for Discrete Mathematics & Theoretical
Computer Science. Preprints DTR-2005-04 and DTR-2006-13 are available at and .
Our co-author Leonid Khachiyan passed away with tragic suddenness on April 29th, 2005. 相似文献
11.
Sandy Irani 《Algorithmica》1994,11(1):53-72
In this paper we consider the problem of on-line graph coloring. In an instance of on-line graph coloring, the nodes are presented one at a time. As each node is presented, its edges to previously presented nodes are also given. Each node must be assigned a color, different from the colors of its neighbors, before the next node is given. LetA(G) be the number of colors used by algorithmA on a graphG and letx(G) be the chromatic number ofG. The performance ratio of an on-line graph coloring algorithm for a class of graphsC is maxG C(A(G)/(G)). We consider the class ofd-inductive graphs. A graphG isd-inductive if the nodes ofG can be numbered so that each node has at mostd edges to higher-numbered nodes. In particular, planar graphs are 5-inductive, and chordal graphs arex(G)-inductive. First Fit is the algorithm that assigns each node the lowest-numbered color possible. We show that ifG isd-inductive, then First Fit usesO(d logn) colors onG. This yields an upper bound ofo(logn) on the performance ratio of First Fit on chordal and planar graphs. First Fit does as well as any on-line algorithm ford-inductive graphs: we show that, for anyd and any on-line graph coloring algorithmA, there is ad-inductive graph that forcesA to use (d logn) colors to colorG. We also examine on-line graph coloring with lookahead. An algorithm is on-line with lookaheadl, if it must color nodei after examining only the firstl+i nodes. We show that, forl/logn, the lower bound ofd logn colors still holds.This research was supported by an IBM Graduate Fellowship. 相似文献
12.
Preemptive and Non-preemptive On-line Algorithms for Scheduling with Rejection on Two Uniform Machines 总被引:1,自引:0,他引:1
In this paper, we consider the problem of on-line scheduling a job sequence on two uniform machines. A job can be either rejected,
in which case we pay its penalty, or scheduled on machines, in which case it contributes its processing time to the makspan
of the constructed schedule. The objective is to minimize the sum of the makespan of the schedule for all accepted jobs and
the penalties of all rejected jobs. Both preemptive and non-preemptive versions are considered. For the preemptive version,
we present an optimal on-line algorithm with a competitive ratio for any s≥1, where s is the machine speed ratio. For the non-preemptive version, we present an improved lower bound. Moreover, as an optimal algorithm
for s≥1.6180 is known, we present a modified version of the known algorithm, and show that it becomes optimal for any 1.3852≤s<1.6180 and has a smaller competitive ratio than that of original version for any 1≤s<1.3852. The maximum gap between its competitive ratio and the lower bound is 0.0534. 相似文献
13.
Counting the number of perfect matchings in graphs is a computationally hard problem. However, in the case of planar graphs, and even for K3,3-free graphs, the number of perfect matchings can be computed efficiently. The technique to achieve this is to compute a Pfaffian orientation of a graph. In the case of K5-free graphs, this technique will not work because some K5-free graphs do not have a Pfaffian orientation. We circumvent this problem and show that the number of perfect matchings in K5-free graphs can be computed in polynomial time. We also parallelize the sequential algorithm and show that the problem is in TC2. We remark that our results generalize to graphs without singly-crossing minor. 相似文献
14.
In a graph G a matching is a set of edges in which no two
edges have a common endpoint. An induced matching is a
matching in which no two edges are linked by an edge of G. The
maximum induced matching (abbreviated MIM) problem is to find the
maximum size of an induced matching for a given graph G. This
problem is known to be NP-hard even on bipartite graphs or on planar
graphs. We present a polynomial time algorithm which given a graph
G either finds a maximum induced matching in G, or claims that the
size of a maximum induced matching in G is strictly less than the
size of a maximum matching in G. We show that the MIM problem is
NP-hard on line-graphs, claw-free graphs, chair-free graphs,
Hamiltonian graphs and r-regular graphs for r \geq 5. On the
other hand, we present polynomial time algorithms for the MIM problem
on (P
5,D
m
)-free graphs, on (bull, chair)-free graphs and on
line-graphs of Hamiltonian graphs. 相似文献
15.
Vicky Choi 《Quantum Information Processing》2011,10(3):343-353
In Choi (Quantum Inf Process, 7:193–209, 2008), we introduced the notion of minor-embedding in adiabatic quantum optimization. A minor-embedding of a graph G in a quantum hardware graph U is a subgraph of U such that G can be obtained from it by contracting edges. In this paper, we describe the intertwined adiabatic quantum architecture design
problem, which is to construct a hardware graph U that satisfies all known physical constraints and, at the same time, permits an efficient minor-embedding algorithm. We illustrate
an optimal complete-graph-minor hardware graph. Given a family F{\mathcal{F}} of graphs, a (host) graph U is called F{\mathcal{F}}-minor-universal if for each graph G in F, U{\mathcal{F}, U} contains a minor-embedding of G. The problem for designing a F{{\mathcal{F}}}-minor-universal hardware graph U
sparse
in which F{{\mathcal{F}}} consists of a family of sparse graphs (e.g., bounded degree graphs) is open. 相似文献
16.
Frdric Maffray 《Information Processing Letters》2009,109(23-24):1235-1237
We show that, for fixed k, there is a polynomial-time algorithm that finds a maximum (or maximum-weight) stable set in any graph that belongs to the class of k-colorable P5-free graphs, or, more generally, to the class of P5-free graphs that contain no clique of size k+1. This is based on the following structural result: every connected k-colorable P5-free graph has a vertex whose non-neighbors induce a (k−1)-colorable subgraph. 相似文献
17.
In automatic graph drawing a given graph has to be laid out in the plane, usually according to a number of topological and aesthetic constraints. Nice drawings for sparse nonplanar graphs can be achieved by determining a maximum planar subgraph and augmenting an embedding of this graph. This approach appears to be of limited value in practice, because the maximum planar subgraph problem is NP-hard.We attack the maximum planar subgraph problem with a branch-and-cut technique which gives us quite good, and in many cases provably optimum, solutions for sparse graphs and very dense graphs. In the theoretical part of the paper, the polytope of all planar subgraphs of a graphG is defined and studied. All subgraphs of a graphG, which are subdivisions ofK
5 orK
3,3, turn out to define facets of this polytope. For cliques contained inG, the Euler inequalities turn out to be facet-defining for the planar subgraph polytope. Moreover, we introduce the subdivision inequalities,V
2k
inequalities, and the flower inequalities, all of which are facet-defining for the polytope. Furthermore, the composition of inequalities by 2-sums is investigated.We also present computational experience with a branch-and-cut algorithm for the above problem. Our approach is based on an algorithm which searches for forbidden substructures in a graph that contains a subdivision ofK
5 orK
3,3. These structures give us inequalities which are used as cutting planes.Finally, we try to convince the reader that the computation of maximum planar subgraphs is indeed a practical tool for finding nice embeddings by applying this method to graphs taken from the literature. 相似文献
18.
Given a graph G=(V,E) with strictly positive integer weights ω
i
on the vertices i∈V, an interval coloring of G is a function I that assigns an interval I(i) of ω
i
consecutive integers (called colors) to each vertex i∈V so that I(i)∩I(j)=∅ for all edges {i,j}∈E. The interval coloring problem is to determine an interval coloring that uses as few colors as possible. Assuming that a
strictly positive integer weight δ
ij
is associated with each edge {i,j}∈E, a bandwidth coloring of G is a function c that assigns an integer (called a color) to each vertex i∈V so that |c(i)−c(j)|≥δ
ij
for all edges {i,j}∈E. The bandwidth coloring problem is to determine a bandwidth coloring with minimum difference between the largest and the
smallest colors used. We prove that an optimal solution of the interval coloring problem can be obtained by solving a series
of bandwidth coloring problems. Computational experiments demonstrate that such a reduction can help to solve larger instances
or to obtain better upper bounds on the optimal solution value of the interval coloring problem. 相似文献
19.
In this paper the coloring problem for unit disk (UD) graphs is considered. UD graphs are the intersection graphs of equal-sized
disks in the plane. Colorings of UD graphs arise in the study of channel assignment problems in broadcast networks. Improving
on a result of Clark et al. [2] it is shown that the coloring problem for UD graphs remains NP-complete for any fixed number of colors k≥ 3 . Furthermore, a new 3-approximation algorithm for the problem is presented which is based on network flow and matching techniques.
Received February 12, 1996; revised October 9, 1996. 相似文献
20.
Given a graph G=(V,E) and two vertices s,t ∈ V , s\neq t , the Menger problem is to find a maximum number of disjoint paths connecting s and t . Depending on whether the input graph is directed or not, and what kind of disjointness criterion is demanded, this general
formulation is specialized to the directed or undirected vertex, and the edge or arc disjoint Menger problem, respectively.
For planar graphs the edge disjoint Menger problem has been solved to optimality [W2], while the fastest algorithm for the
arc disjoint version is Weihe's general maximum flow algorithm for planar networks [W1], which has running time \bf O (|V| log |V|) . Here we present a linear time, i.e., asymptotically optimal, algorithm for the arc disjoint version in planar directed
graphs.
Received August 1997; revised January 1999. 相似文献