共查询到20条相似文献,搜索用时 12 毫秒
1.
Motivated by applications in software programming, we consider the problem of covering a graph by a feasible labeling. Given an undirected graph G=(V,E), two positive integers k and t, and an alphabet Σ, a feasible labeling is defined as an assignment of a set Lv⊆Σ to each vertex v∈V, such that (i) |Lv|≤k for all v∈V and (ii) each label α∈Σ is used no more than t times. An edge e={i,j} is said to be covered by a feasible labeling if Li∩Lj≠0?. G is said to be covered if there exists a feasible labeling that covers each edge e∈E.In general, we show that the problem of deciding whether or not a tree can be covered is strongly NP-complete. For k=2, t=3, we characterize the trees that can be covered and provide a linear time algorithm for solving the decision problem. For fixed t, we present a strongly polynomial algorithm that solves the decision problem; if a tree can be covered, then a corresponding feasible labeling can be obtained in time polynomial in k and the size of the tree. For general graphs, we give a strongly polynomial algorithm to resolve the covering problem for k=2, t=3. 相似文献
2.
《Discrete Mathematics》2022,345(7):112893
In this paper, we study the Reconstruction Conjecture for finite simple graphs. Let Γ and be finite simple graphs with at least three vertices such that there exists a bijective map and for any , there exists an isomorphism . Then we define the associated directed graph with two kinds of arrows from the graphs Γ and , the bijective map f and the isomorphisms . By investigating the associated directed graph , we study when are the two graphs Γ and isomorphic. 相似文献
3.
Michael v. Rimscha 《Combinatorica》1984,4(4):339-343
We are concerned with the notion of the degree-type (D G i )i∈ω of a graphG, whereD G i is defined to be the number of vertices inG with degreei. In the first section the following results are proven:
- IfG is a connected, locally finite, countably infinite graph such that there exists ani so thatD G i andD G i+1 are both finite and different from 0, thenG is reconstructible.
- Locally finite, countably infinite graphsG, for which infinitely manyD G i are different from 0 but only finitely manyD G i are infinite, are reconstructible.
4.
Christian Sommer 《Discrete Mathematics》2009,309(10):3381-3384
Coja-Oghlan and Taraz [Amin Coja-Oghlan, Anusch Taraz, Exact and approximative algorithms for coloring , Random Structures and Algorithms 24 (3) (2004) 259-278] presented a graph coloring algorithm that has expected linear running time for random graphs with edge probability p satisfying np≤1.01. In this work, we develop their analysis by exploiting generating function techniques. We show that, in fact, their algorithm colors Gn,p with the minimal number of colors and has expected linear running time, provided that np≤1.33. 相似文献
5.
J. Nagy-György 《Operations Research Letters》2010,38(3):185-187
We give an upper bound for the online chromatic number of graphs with high girth and for graphs with high odd girth generalizing Kierstead’s algorithm for graphs that contain neither a C3 or C5 as an induced subgraph. 相似文献
6.
We present a polynomial-time approximation algorithm for legally coloring as many edges of a given simple graph as possible using two colors. It achieves an approximation ratio of roughly 0.842 and runs in O(n3m) time, where n (respectively, m) is the number of vertices (respectively, edges) in the input graph. The previously best ratio achieved by a polynomial-time approximation algorithm was . 相似文献
7.
Lilian Markenzon Oswaldo Vernet Luiz Henrique Araujo 《Annals of Operations Research》2008,157(1):47-60
In this paper two methods for automatic generation of connected chordal graphs are proposed: the first one is based on new
results concerning the dynamic maintenance of chordality under edge insertions; the second is based on expansion/merging of
maximal cliques. Theoretical and experimental results are presented. In both methods, chordality is preserved along the whole
generation process.
L. Markenzon’s research is partially supported by grant 301068/2003-8, CNPq, Brazil. 相似文献
8.
In this paper, we first present an O(n+m)-time sequential algorithm to solve the Hamiltonian problem on a distance-hereditary graph G, where n and m are the number of vertices and edges of G, respectively. This algorithm is faster than the previous best known algorithm for the problem which takes O(n2) time. We also give an efficient parallel implementation of our sequential algorithm. Moreover, if G is represented by its decomposition tree form, the problem can be solved optimally in O(logn) time using O((n+m)/logn) processors on an EREW PRAM. 相似文献
9.
Darryn Bryant 《Journal of Combinatorial Theory, Series A》2010,117(8):1258-1284
Let m1,m2,…,mt be a list of integers. It is shown that there exists an integer N such that for all n?N, the complete graph of order n can be decomposed into edge-disjoint cycles of lengths m1,m2,…,mt if and only if n is odd, 3?mi?n for i=1,2,…,t, and . In 1981, Alspach conjectured that this result holds for all n, and that a corresponding result also holds for decompositions of complete graphs of even order into cycles and a perfect matching. 相似文献
10.
A graph is k-linked if for every set of 2k distinct vertices {s1,…,sk,t1,…,tk} there exist disjoint paths P1,…,Pk such that the endpoints of Pi are si and ti. We prove every 6-connected graph on n vertices with 5n−14 edges is 3-linked. This is optimal, in that there exist 6-connected graphs on n vertices with 5n−15 edges that are not 3-linked for arbitrarily large values of n. 相似文献
11.
We show that almost surely the rank of the adjacency matrix of the Erd?s‐Rényi random graph G(n,p) equals the number of nonisolated vertices for any c ln n/n ≤ p ≤ 1/2, where c is an arbitrary positive constant larger than 1/2. In particular, the adjacency matrix of the giant component (a.s.) has full rank in this range. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008 相似文献
12.
A path cover of a graph G=(V,E) is a family of vertex-disjoint paths that covers all vertices in V. Given a graph G, the path cover problem is to find a path cover of minimum cardinality. This paper presents a simple O(n)-time approximation algorithm for the path cover problem on circular-arc graphs given a set of n arcs with endpoints sorted. The cardinality of the path cover found by the approximation algorithm is at most one more than the optimal one. By using the result, we reduce the path cover problem on circular-arc graphs to the Hamiltonian cycle and Hamiltonian path problems on the same class of graphs in O(n) time. Hence the complexity of the path cover problem on circular-arc graphs is the same as those of the Hamiltonian cycle and Hamiltonian path problems on circular-arc graphs. 相似文献
13.
We describe an algorithm for the dominating set problem with time complexity O((4g+40)kn2) for graphs of bounded genus g1, where k is the size of the set. It has previously been shown that this problem is fixed parameter tractable for planar graphs. We give a simpler proof for the previous O(8kn2) result for planar graphs. Our method is a refinement of the earlier techniques. 相似文献
14.
Edith Hemaspaandra Lane A. Hemaspaandra Stanis?aw P. Radziszowski 《Discrete Applied Mathematics》2007,155(2):103-118
We investigate the relative complexity of the graph isomorphism problem (GI) and problems related to the reconstruction of a graph from its vertex-deleted or edge-deleted subgraphs (in particular, deck checking (DC) and legitimate deck (LD) problems). We show that these problems are closely related for all amounts c?1 of deletion:
- (1)
- , , , and .
- (2)
- For all k?2, and .
- (3)
- For all k?2, .
- (4)
- .
- (5)
- For all k?2, .
15.
Jochen Alber Jií Fiala 《Journal of Algorithms in Cognition, Informatics and Logic》2004,52(2):134-151
We consider the parameterized problem, whether for a given set
of n disks (of bounded radius ratio) in the Euclidean plane there exists a set of k non-intersecting disks. For this problem, we expose an algorithm running in time
that is—to our knowledge—the first algorithm with running time bounded by an exponential with a sublinear exponent. For λ-precision disk graphs of bounded radius ratio, we show that the problem is fixed parameter tractable with a running time
. The results are based on problem kernelization and a new “geometric (
-separator) theorem” which holds for all disk graphs of bounded radius ratio. The presented algorithm then performs, in a first step, a “geometric problem kernelization” and, in a second step, uses divide-and-conquer based on our new “geometric separator theorem.” 相似文献
16.
Chandra Mohan Krishnamurthy R. Sritharan 《Discrete Applied Mathematics》2012,160(3):224-230
We show that the maximum induced matching problem can be solved on hhd-free graphs in O(m2) time; hhd-free graphs generalize chordal graphs and the previous best bound was O(m3). Then, we consider a technique used by Brandstädt and Hoàng (2008) [4] to solve the problem on chordal graphs. Extending this, we show that for a subclass of hhd-free graphs that is more general than chordal graphs the problem can be solved in linear time. We also present examples to demonstrate the tightness of our results. 相似文献
17.
Ekkehard Khler 《Journal of Discrete Algorithms》2004,2(4):439-452
We consider the problem of recognizing AT-free graphs. Although there is a simple O(n3) algorithm, no faster method for solving this problem had been known. Here we give three different algorithms which have a better time complexity for graphs which are sparse or have a sparse complement; in particular we give algorithms which recognize AT-free graphs in
,
, and O(n2.82+nm). In addition we give a new characterization of graphs with bounded asteroidal number by the help of the knotting graph, a combinatorial structure which was introduced by Gallai for considering comparability graphs. 相似文献
18.
Given a graph and a length function defined on its edge-set, the Traveling Salesman Problem can be described as the problem of finding a family of edges (an edge may be chosen several times) which forms a spanning Eulerian subgraph of minimum length. In this paper we characterize those graphs for which the convex hull of all solutions is given by the nonnegativity constraints and the classical cut constraints. This characterization is given in terms of excluded minors. A constructive characterization is also given which uses a small number of basic graphs. 相似文献
19.
With the notation
,we prove the following result.Theorem 1. Assume that p is a trigonometric polynomial of degree at most n with real coefficients that satisfiesThenwithWe also prove thatandfor every
, where
denotes the collection of all trigonometric polynomials of the form 相似文献
||p||L2(K)An1/2 and ||p′||L2(K)Bn3/2.
M4(p)−M2(p)M2(p)
M2(p)−M1(p)10−31M2(p)