共查询到20条相似文献,搜索用时 15 毫秒
1.
Minghui Jiang 《Algorithmica》2013,66(3):541-563
A d-interval is the union of d disjoint intervals on the real line. A d-track interval is the union of d disjoint intervals on d disjoint parallel lines called tracks, one interval on each track. As generalizations of the ubiquitous interval graphs, d-interval graphs and d-track interval graphs have wide applications, traditionally to scheduling and resource allocation, and more recently to bioinformatics. In this paper, we prove that recognizing d-track interval graphs is NP-complete for any constant d≥2. This confirms a conjecture of Gyárfás and West in 1995. Previously only the complexity of the case d=2 was known. Our proof in fact implies that several restricted variants of this graph recognition problem, i.e., recognizing balanced d-track interval graphs, unit d-track interval graphs, and (2,…,2) d-track interval graphs, are all NP-complete. This partially answers another question recently raised by Gambette and Vialette. We also prove that recognizing depth-two 2-track interval graphs is NP-complete, even for the unit case. In sharp contrast, we present a simple linear-time algorithm for recognizing depth-two unit d-interval graphs. These and other results of ours give partial answers to a question of West and Shmoys in 1984 and a similar question of Gyárfás and West in 1995. Finally, we give the first bounds on the track number and the unit track number of a graph in terms of the number of vertices, the number of edges, and the maximum degree, and link the two numbers to the classical concepts of arboricity. 相似文献
2.
Andreas Brandstadt Feodor F. Dragan Hoang-Oanh Le Van Bang Le Ryuhei Uehara 《Algorithmica》2007,47(1):27-51
A tree t-spanner T in a graph G is a spanning tree of G such that the distance between every pair of vertices in T is at most
t times their distance in G. The tree t-spanner problem asks whether a graph admits a tree t-spanner, given t. We first substantially
strengthen the known results for bipartite graphs. We prove that the tree t-spanner problem is NP-complete even for chordal
bipartite graphs for t ≥ 5, and every bipartite ATE-free graph has a tree 3-spanner, which can be found in linear time. The
previous best known results were NP-completeness for general bipartite graphs, and that every convex graph has a tree 3-spanner.
We next focus on the tree t-spanner problem for probe interval graphs and related graph classes. The graph classes were introduced
to deal with the physical mapping of DNA. From a graph theoretical point of view, the classes are natural generalizations
of interval graphs. We show that these classes are tree 7-spanner admissible, and a tree 7-spanner can be constructed in (m
log n) time. 相似文献
3.
4.
The Complexity of Interval Routing on Random Graphs 总被引:1,自引:0,他引:1
5.
In this paper, we consider the on-line scheduling of jobs that may be competing for mutually exclusive resources. We model the conflicts between jobs with a conflict graph, so that the set of all concurrently running jobs must form an independent set in the graph. This model is natural and general enough to have applications in a variety of settings; however, we are motivated by the following two specific applications: traffic intersection control and session scheduling in high speed local area networks with spatial reuse. Our results focus on two special classes of graphs motivated by our applications: bipartite graphs and interval graphs. The cost function we use is maximum response time. In all of the upper bounds, we devise algorithms which maintain a set of invariants which bound the accumulation of jobs on cliques (in the case of bipartite graphs, edges) in the graph. The lower bounds show that the invariants maintained by the algorithms are tight to within a constant factor. For a specific graph which arises in the traffic intersection control problem, we show a simple algorithm which achieves the optimal competitive ratio. 相似文献
6.
In this paper we study the following NP-complete problem: given an interval graph G = (V,E) , find a node p -coloring such that the cost is minimal, where denotes a partition of V whose subsets are ordered by nonincreasing cardinality. We present an O(m
χ
(G) + n log n) time ε -approximate algorithm (ε < 2) to solve the problem, where n , m , and χ #(G) are the number of nodes of the interval graph, its number of cliques, and its chromatic number, respectively. The
algorithm is shown to solve the problem exactly on some classes of interval graphs, namely, the proper and the containment
interval graphs, and the intersection graphs of sets of ``short' intervals. The problem of determining the minimum number
of colors needed to achieve the minimum over all p -colorings of G is also addressed.
Received February 1, 1996; revised August 22, 1997. 相似文献
7.
8.
Louis Ibarra 《Algorithmica》2010,58(3):637-678
We present the first dynamic graph algorithm for recognizing interval graphs. The algorithm runs in O(nlog?n) worst-case time per edge deletion or edge insertion, where n is the number of vertices in the graph. The algorithm uses a new representation of interval graphs called the train tree, which is based on the clique-separator graph representation of chordal graphs. The train tree has a number of useful properties and it can be constructed from the clique-separator graph in O(n) time. 相似文献
9.
提出一个解带权区间图的最短路问题的O(nα(n))时间新算法,其中n是带权区间图中带权区间的个数,α(n)是单变量Ackerman函数的逆函数,它是一个增长速度比log n慢得多的函数,对于通常所见到的n,α(n)≤4.本文提出的新算法不仅在时间复杂性上比直接用Dijkstra算法解带权区间图的最短路问题有较大改进,而且算法设计思想简单,易于理解和实现. 相似文献
10.
The longest path problem is the problem of finding a path of maximum length in a graph. Polynomial solutions for this problem
are known only for small classes of graphs, while it is NP-hard on general graphs, as it is a generalization of the Hamiltonian
path problem. Motivated by the work of Uehara and Uno (Proc. of the 15th Annual International Symp. on Algorithms and Computation
(ISAAC), LNCS, vol. 3341, pp. 871–883, 2004), where they left the longest path problem open for the class of interval graphs, in this paper we show that the problem
can be solved in polynomial time on interval graphs. The proposed algorithm uses a dynamic programming approach and runs in
O(n
4) time, where n is the number of vertices of the input graph. 相似文献
11.
Given a set of n intervals representing an interval graph, the problem of finding a maximum matching between pairs of disjoint (nonintersecting)
intervals has been considered in the sequential model. In this paper we present parallel algorithms for computing maximum
cardinality matchings among pairs of disjoint intervals in interval graphs in the EREW PRAM and hypercube models. For the
general case of the problem, our algorithms compute a maximum matching in O( log
3
n) time using O(n/ log
2
n) processors on the EREW PRAM and using n processors on the hypercubes. For the case of proper interval graphs, our algorithm runs in O( log n ) time using O(n) processors if the input intervals are not given already sorted and using O(n/ log n ) processors otherwise, on the EREW PRAM. On n -processor hypercubes, our algorithm for the proper interval case takes O( log n log log n ) time for unsorted input and O( log n ) time for sorted input. Our parallel results also lead to optimal sequential algorithms for computing maximum matchings
among disjoint intervals. In addition, we present an improved parallel algorithm for maximum matching between overlapping
intervals in proper interval graphs.
Received November 20, 1995; revised September 3, 1998. 相似文献
12.
We consider the sum coloring and sum multicoloring problems on several
fundamental classes of graphs, including the classes of interval and
k-claw free graphs. We give an algorithm that approximates sum coloring
within a factor of 1.796, for any graph in which the maximum k-colorable
subgraph problem is polynomially solvable. In particular, this improves on
the previous best known ratio of 2 for interval graphs. We introduce a new
measure of coloring, robust throughput}, that indicates how quickly
the graph is colored, and show that our algorithm approximates this measure
within a factor of 1.4575.
In addition, we study the contiguous (or non-preemptive) sum multicoloring
problem on k-claw free graphs.
This models, for example,
the scheduling of dependent jobs on multiple dedicated machines, where each job
requires the exclusive use of at most k machines.
Assuming that k is a fixed constant,
we obtain the first constant factor approximation for the problem. 相似文献
13.
14.
15.
16.
17.
The study of infinite graphs has potential applications in the specification and verification of infinite systems and in
the transformation of such systems. Prefix-recognizable graphs and regular graphs are of particular interest in this area
since their monadic second-order theories are decidable. Although the latter form a proper subclass of the former, no characterization
of regular graphs within the class of prefix-recognizable ones has been known, except for a graph-theoretic one in [2]. We
provide here three such new characterizations. In particular, a decidable, language-theoretic, necessary and sufficient condition
for the regularity of any prefix-recognizable graph is established. Our proofs yield a construction of a deterministic hyperedge-replacement
grammar for any prefix-recognizable graph that is regular.
Received July 19, 1999, and in revised form December 22, 2000, and in final form March 28, 2001. Online publication July
20, 2001. 相似文献
18.
Thomas Andreae Michael Nölle Gerald Schreiber 《Journal of Parallel and Distributed Computing》1997,46(2):531
Given a Cartesian productG=G1× … ×Gm(m≥ 2) of nontrivial connected graphsGiand then-dimensional baseBde Bruijn graphD=DB(n), it is investigated whether or notGis a spanning subgraph ofD. Special attention is given to graphsG1× … ×Gmwhich are relevant for parallel computing, namely, to Cartesian products of paths (grids) or cycles (tori). For 2-dimensional de Bruijn graphsD, we present a theorem stating that certain structural assumptions on the factorsG1, …,Gmensure thatG1× … ×Gmis a spanning subgraph ofD. As corollaries, we obtain results improving previous results of Heydemannet al.(J. Parallel Distrib. Comput.23 (1994), 104–111) on embedding grids and tori into de Bruijn graphs. Specifically, we obtain that (i) any gridG=G1× … ×Gmis a spanning subgraph ofD=DB(2) provided that |G| = |D|, and (ii) any torusG=G1× … ×Gmis a spanning subgraph ofD=DB(2) provided that |G| = |D| and that theGiare cycles of even length ≥4. We show that these results have consequences for the casen> 2, too: for evenn, we apply our results to obtain embeddings of grids and toriGinto de Bruijn graphsDB(n) with dilationn/2, where the baseBis a fixed integer ≥2, andnis big enough to ensure |G| ≤ |DB(n)|. We also contrast our results forn= 2 with nonexistence results forn≥ 3 and briefly describe experimental results in the area of parallel image processing. 相似文献
19.
Hierarchical graphs and clustered graphs are useful non-classical graph models for structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures. Both have applications in CASE tools, software visualization and VLSI design. Drawing algorithms for hierarchical graphs have been well investigated. However, the problem of planar straight-line representation has not been solved completely. In this paper we answer the question: does every planar hierarchical graph admit a planar straight-line hierarchical drawing? We present an algorithm that constructs such drawings in linear time. Also, we answer a basic question for clustered graphs, that is, does every planar clustered graph admit a planar straight-line drawing with clusters drawn as convex polygons? We provide a method for such drawings based on our algorithm for hierarchical graphs. 相似文献
20.
Interval Routing 总被引:3,自引:0,他引:3