共查询到20条相似文献,搜索用时 0 毫秒
1.
Guillermo Durán Min Chih Lin Sergio Mera Jayme Luiz Szwarcfiter 《Discrete Applied Mathematics》2006,154(13):1783-1790
A circular-arc graph is the intersection graph of arcs on a circle. A Helly circular-arc graph is a circular-arc graph admitting a model whose arcs satisfy the Helly property. A clique-independent set of a graph is a set of pairwise disjoint cliques of the graph. It is NP-hard to compute the maximum cardinality of a clique-independent set for a general graph. In the present paper, we propose polynomial time algorithms for finding the maximum cardinality and weight of a clique-independent set of a -free CA graph. Also, we apply the algorithms to the special case of an HCA graph. The complexity of the proposed algorithm for the cardinality problem in HCA graphs is O(n). This represents an improvement over the existing algorithm by Guruswami and Pandu Rangan, whose complexity is O(n2). These algorithms suppose that an HCA model of the graph is given. 相似文献
2.
Flavia Bonomo 《Discrete Mathematics》2006,306(6):595-597
A clique in a graph is a complete subgraph maximal under inclusion. The clique graph of a graph is the intersection graph of its cliques. A graph is self-clique when it is isomorphic to its clique graph. A circular-arc graph is the intersection graph of a family of arcs of a circle. A Helly circular-arc graph is a circular-arc graph admitting a model whose arcs satisfy the Helly property. In this note, we describe all the self-clique Helly circular-arc graphs. 相似文献
3.
We give two new linear-time algorithms, one for recognizing proper circular-arc graphs and the other for recognizing unit circular-arc graphs. Both algorithms provide either a model for the input graph, or a certificate that proves that such a model does not exist and can be authenticated in O(n) time. No other previous algorithm for each of these two graph classes provides a certificate for its result. 相似文献
4.
A clique-transversal of a graph G is a subset of vertices that meets all the cliques of G. A clique-independent set is a collection of pairwise vertex-disjoint cliques. A graph G is clique-perfect if the sizes of a minimum clique-transversal and a maximum clique-independent set are equal for every induced subgraph of G. The list of minimal forbidden induced subgraphs for the class of clique-perfect graphs is not known. Another open question concerning clique-perfect graphs is the complexity of the recognition problem. Recently we were able to characterize clique-perfect graphs by a restricted list of forbidden induced subgraphs when the graph belongs to two different subclasses of claw-free graphs. These characterizations lead to polynomial time recognition of clique-perfect graphs in these classes of graphs. In this paper we solve the characterization problem in two new classes of graphs: diamond-free and Helly circular-arc () graphs. This last characterization leads to a polynomial time recognition algorithm for clique-perfect graphs. 相似文献
5.
A locally connected spanning tree of a graph G is a spanning tree T of G such that the set of all neighbors of v in T induces a connected subgraph of G for every v∈V(G). The purpose of this paper is to give linear-time algorithms for finding locally connected spanning trees on strongly chordal graphs and proper circular-arc graphs, respectively. 相似文献
6.
Mitre C. Dourado Fábio Protti Jayme L. Szwarcfiter 《Discrete Applied Mathematics》2007,155(18):2435-2443
Let p?1 and q?0 be integers. A family of sets F is (p,q)-intersecting when every subfamily F′⊆F formed by p or less members has total intersection of cardinality at least q. A family of sets F is (p,q)-Helly when every (p,q)-intersecting subfamily F′⊆F has total intersection of cardinality at least q. A graph G is a (p,q)-clique-Helly graph when its family of (maximal) cliques is (p,q)-Helly. According to this terminology, the usual Helly property and the clique-Helly graphs correspond to the case p=2,q=1. In this work we present a characterization for (p,q)-clique-Helly graphs. For fixed p,q, this characterization leads to a polynomial-time recognition algorithm. When p or q is not fixed, it is shown that the recognition of (p,q)-clique-Helly graphs is NP-hard. 相似文献
7.
A graph is perfect if the chromatic number is equal to the clique number for every induced subgraph of the graph. Perfect graphs were defined by Berge in the sixties. In this survey we present known results about partial characterizations by forbidden induced subgraphs of different graph classes related to perfect graphs. We analyze a variation of perfect graphs, clique-perfect graphs, and two subclasses of perfect graphs, coordinated graphs and balanced graphs. 相似文献
8.
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. 相似文献
9.
A circular-arc graphG is the intersection graph of a collection of arcs on the circle and such a collection is called a model of G. Say that the model is proper when no arc of the collection contains another one, it is Helly when the arcs satisfy the Helly Property, while the model is proper Helly when it is simultaneously proper and Helly. A graph admitting a Helly (resp. proper Helly) model is called a Helly (resp. proper Helly) circular-arc graph. The clique graphK(G) of a graph G is the intersection graph of its cliques. The iterated clique graphKi(G) of G is defined by K0(G)=G and Ki+1(G)=K(Ki(G)). In this paper, we consider two problems on clique graphs of circular-arc graphs. The first is to characterize clique graphs of Helly circular-arc graphs and proper Helly circular-arc graphs. The second is to characterize the graph to which a general circular-arc graph K-converges, if it is K-convergent. We propose complete solutions to both problems, extending the partial results known so far. The methods lead to linear time recognition algorithms, for both problems. 相似文献
10.
Frédéric Gardi 《Discrete Mathematics》2007,307(22):2906-2908
In this note, a constructive proof that the classes of proper interval graphs and unit interval graphs coincide is given, a result originally established by Fred S. Roberts. Additionally, the proof yields a linear-time and space algorithm to compute a unit interval representation, given a proper interval graph as input. 相似文献
11.
Nicola Apollonio 《Discrete Applied Mathematics》2011,159(11):1166-1175
We present a unifying procedure for recognizing intersection graphs of Helly families of paths in a tree and their clique graphs. The Helly property makes it possible to look at these recognition problems as variants of the Graph Realization Problem, namely, the problem of recognizing Edge-Path-Tree matrices. Our result heavily relies on the notion of pie introduced in [M.C. Golumbic, R.E. Jamison, The edge intersection graphs of paths in a tree, Journal of Combinatorial Theory, Series B 38 (1985) 8-22] and on the observation that Helly Edge-Path-Tree matrices form a self-dual class of Helly matrices. Coupled to the notion of reduction presented in the paper, these facts are also exploited to reprove and slightly refine some known results for Edge-Path-Tree graphs. 相似文献
12.
13.
Guillermo Durán Min Chih Lin Sergio Mera Jayme L. Szwarcfiter 《Annals of Operations Research》2008,157(1):37-45
A clique-transversal of a graph G is a subset of vertices intersecting all the cliques of G. It is NP-hard to determine the minimum cardinality τ
c
of a clique-transversal of G. In this work, first we propose an algorithm for determining this parameter for a general graph, which runs in polynomial
time, for fixed τ
c
. This algorithm is employed for finding the minimum cardinality clique-transversal of
[`(3K2)]\overline{3K_{2}}
-free circular-arc graphs in O(n
4) time. Further we describe an algorithm for determining τ
c
of a Helly circular-arc graph in O(n) time. This represents an improvement over an existing algorithm by Guruswami and Pandu Rangan which requires O(n
2) time. Finally, the last proposed algorithm is modified, so as to solve the weighted version of the corresponding problem,
in O(n
2) time. 相似文献
14.
A blocking quadruple (BQ) is a quadruple of vertices of a graph such that any two vertices of the quadruple either miss (have no neighbours on) some path connecting the remaining two vertices of the quadruple, or are connected by some path missed by the remaining two vertices. This is akin to the notion of asteroidal triple used in the classical characterization of interval graphs by Lekkerkerker and Boland [Klee, V., What are the intersection graphs of arcs in a circle?, American Mathematical Monthly 76 (1976), pp. 810–813.].In this note, we first observe that blocking quadruples are obstructions for circular-arc graphs. We then focus on chordal graphs, and study the relationship between the structure of chordal graphs and the presence/absence of blocking quadruples.Our contribution is two-fold. Firstly, we provide a forbidden induced subgraph characterization of chordal graphs without blocking quadruples. In particular, we observe that all the forbidden subgraphs are variants of the subgraphs forbidden for interval graphs [Klee, V., What are the intersection graphs of arcs in a circle?, American Mathematical Monthly 76 (1976), pp. 810–813.]. Secondly, we show that the absence of blocking quadruples is sufficient to guarantee that a chordal graph with no independent set of size five is a circular-arc graph. In our proof we use a novel geometric approach, constructing a circular-arc representation by traversing around a carefully chosen clique tree. 相似文献
15.
Liliana Alcón 《Discrete Applied Mathematics》2006,154(13):1799-1802
The clique graph of G, K(G), is the intersection graph of the family of cliques (maximal complete sets) of G. Clique-critical graphs were defined as those whose clique graph changes whenever a vertex is removed. We prove that if G has m edges then any clique-critical graph in K-1(G) has at most 2m vertices, which solves a question posed by Escalante and Toft [On clique-critical graphs, J. Combin. Theory B 17 (1974) 170-182]. The proof is based on a restatement of their characterization of clique-critical graphs. Moreover, the bound is sharp. We also show that the problem of recognizing clique-critical graphs is NP-complete. 相似文献
16.
Pinar Heggernes 《Discrete Mathematics》2006,306(3):297-317
Any given graph can be embedded in a chordal graph by adding edges, and the resulting chordal graph is called a triangulation of the input graph. In this paper we study minimal triangulations, which are the result of adding an inclusion minimal set of edges to produce a triangulation. This topic was first studied from the standpoint of sparse matrices and vertex elimination in graphs. Today we know that minimal triangulations are closely related to minimal separators of the input graph. Since the first papers presenting minimal triangulation algorithms appeared in 1976, several characterizations of minimal triangulations have been proved, and a variety of algorithms exist for computing minimal triangulations of both general and restricted graph classes. This survey presents and ties together these results in a unified modern notation, keeping an emphasis on the algorithms. 相似文献
17.
Atif Abueida 《Discrete Mathematics》2006,306(17):2108-2110
We show that bisplit graphs can be recognized in O(n2) time. The previous best bound of O(mn) for the problem appeared in a recently published article [A. Brandstädt, P.L. Hammer, V.B. Le, V.V. Lozin, Bisplit graphs, Discrete Math. 299 (2005) 11-32] in this journal. 相似文献
18.
We give a simple algorithm for finding a minimum weight odd circuit in planar graphs. By geometric duality, the same algorithm can be used to find minimum weight odd cuts. For general sparse graphs, the fastest known algorithms for these two problems take time and time, respectively. 相似文献
19.
The edge-intersection graph of a family of paths on a host tree is called an graph. When the tree has maximum degree , we say that the graph is . If, in addition, the family of paths satisfies the Helly property, then the graph is Helly . In this paper, we present a family of graphs called gates which are forbidden induced subgraphs for graphs. Using these we characterize by forbidden induced subgraphs the Helly graphs. As a byproduct we prove that in getting a Helly -representation, it is not necessary to increase the maximum degree of the host tree. In addition, we give an efficient algorithm to recognize Helly graphs based on their decomposition by maximal clique separators. 相似文献
20.
Martín D. Safe 《Journal of Graph Theory》2020,93(2):268-298
A graph is concave-round if its vertices can be circularly enumerated so that the closed neighborhood of each vertex is an interval in the enumeration. In this study, we give a minimal forbidden induced subgraph characterization for the class of concave-round graphs, solving a problem posed by Bang-Jensen, Huang, and Yeo [SIAM J. Discrete Math., 13 (2000), pp. 179–193]. In addition, we show that it is possible to find one such forbidden induced subgraph in linear time in any given graph that is not concave-round. As part of the analysis, we obtain characterizations by minimal forbidden submatrices for the circular-ones property for rows and for the circular-ones property for rows and columns and show that, also for both variants of the property, one of the corresponding forbidden submatrices can be found (if present) in any given matrix in linear time. We make some final remarks regarding connections to some classes of circular-arc graphs. 相似文献