Log in

Relevant bibliographies by topics / Chordal graph / Journal articles

To see the other types of publications on this topic, follow the link: Chordal graph.

Journal articles on the topic 'Chordal graph'

Author: Grafiati

Published: 4 June 2021

Last updated: 25 April 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Chordal graph.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Jeya Jothi, R. Mary, and A. Amutha. "Characterization of Super Strongly Perfect Graphs in Chordal and Strongly Chordal Graphs." Mapana - Journal of Sciences 11, no. 4 (September 25, 2012): 121–31. http://dx.doi.org/10.12723/mjs.23.10.

Full text

Abstract:

A Graph G is Super Strongly Perfect Graph if every induced sub graph H of G possesses a minimal dominating set that meets all the maximal complete sub graphs of H. In this paper, we have investigated the characterization of Super Strongly Perfect graphs using odd cycles. We have given the characterization of Super Strongly Perfect graphs in chordal and strongly chordal graphs. We have presented the results of Chordal graphs in terms of domination and co - domination numbers γ and . We have given the relationship between diameter, domination and co - domination numbers of chordal graphs. Also we have analysed the structure of Super Strongly Perfect Graph in Chordal graphs and Strongly Chordal graphs.

APA, Harvard, Vancouver, ISO, and other styles

2

Nguyen, Ngoc Tuy, Jörg Bornemann, and Van Bang Le. "Graph classes related to chordal graphs and chordal bipartite graphs." Electronic Notes in Discrete Mathematics 27 (October 2006): 73–74. http://dx.doi.org/10.1016/j.endm.2006.08.062.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Şeker, Oylum, Pinar Heggernes, Tinaz Ekim, and Z. Caner Taşkın. "Generation of random chordal graphs using subtrees of a tree." RAIRO - Operations Research 56, no. 2 (March 2022): 565–82. http://dx.doi.org/10.1051/ro/2022027.

Full text

Abstract:

Chordal graphs form one of the most studied graph classes. Several graph problems that are NP-hard in general become solvable in polynomial time on chordal graphs, whereas many others remain NP-hard. For a large group of problems among the latter, approximation algorithms, parameterized algorithms, and algorithms with moderately exponential or sub-exponential running time have been designed. Chordal graphs have also gained increasing interest during the recent years in the area of enumeration algorithms. Being able to test these algorithms on instances of chordal graphs is crucial for understanding the concepts of tractability of hard problems on graph classes. Unfortunately, only few published papers give algorithms for generating chordal graphs. Even in these papers, only very few methods aim for generating a large variety of chordal graphs. Surprisingly, none of these methods is directly based on the “intersection of subtrees of a tree” characterization of chordal graphs. In this paper, we give an algorithm for generating chordal graphs, based on the characterization that a graph is chordal if and only if it is the intersection graph of subtrees of a tree. Upon generating a random host tree, we give and test various methods that generate subtrees of the host tree. We compare our methods to one another and to existing ones for generating chordal graphs. Our experiments show that one of our methods is able to generate the largest variety of chordal graphs in terms of maximal clique sizes. Moreover, two of our subtree generation methods result in an overall complexity of our generation algorithm that is the best possible time complexity for a method generating the entire node set of subtrees in an “intersection of subtrees of a tree” representation. The instances corresponding to the results presented in this paper, and also a set of relatively small-sized instances are made available online.

APA, Harvard, Vancouver, ISO, and other styles

4

Uehara, Ryuhei, Seinosuke Toda, and Takayuki Nagoya. "Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs." Discrete Applied Mathematics 145, no. 3 (January 2005): 479–82. http://dx.doi.org/10.1016/j.dam.2004.06.008.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Bermudo, Sergio, Walter Carballosa, José Rodríguez, and José Sigarreta. "On the hyperbolicity of edge-chordal and path-chordal graphs." Filomat 30, no. 9 (2016): 2599–607. http://dx.doi.org/10.2298/fil1609599b.

Full text

Abstract:

If X is a geodesic metric space and x1, x2, x3 ( X, a geodesic triangle T = {x1, x2, x3} is the union of the three geodesics [x1x2], [x2x3] and [x3x1] in X. The space X is ?-hyperbolic (in the Gromov sense) if any side of T is contained in a ?-neighborhood of the union of the other two sides, for every geodesic triangle T in X. An important problem in the study of hyperbolic graphs is to relate the hyperbolicity with some classical properties in graph theory. In this paper we find a very close connection between hyperbolicity and chordality: we extend the classical definition of chordality in two ways, edge-chordality and path-chordality, in order to relate this propertywith Gromov hyperbolicity. In fact, we prove that every edge-chordal graph is hyperbolic and that every hyperbolic graph is path-chordal. Furthermore, we prove that every path-chordal cubic graph with small path-chordality constant is hyperbolic.

APA, Harvard, Vancouver, ISO, and other styles

6

Nisse, Nicolas. "Connected graph searching in chordal graphs." Discrete Applied Mathematics 157, no. 12 (June 2009): 2603–10. http://dx.doi.org/10.1016/j.dam.2008.08.007.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Bender, E. A., L. B. Richmond, and N. C. Wormald. "Almost all chordal graphs split." Journal of the Australian Mathematical Society. Series A. Pure Mathematics and Statistics 38, no. 2 (April 1985): 214–21. http://dx.doi.org/10.1017/s1446788700023077.

Full text

Abstract:

AbstractA chordal graph is a graph in which every cycle of length at least 4 has a chord. If G is a random n-vertex labelled chordal graph, the size of the larget clique in about n/2 and deletion of this clique almost surely leaves only isolated vertices. This gives the asymptotic number of chordal graphs and information about a variety of things such as the size of the largest clique and connectivity.

APA, Harvard, Vancouver, ISO, and other styles

8

Sun, Wenbo, and Ivona Bezáková. "Sampling Random Chordal Graphs by MCMC (Student Abstract)." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 10 (April 3, 2020): 13929–30. http://dx.doi.org/10.1609/aaai.v34i10.7237.

Full text

Abstract:

Chordal graphs are a widely studied graph class, with applications in several areas of computer science, including structural learning of Bayesian networks. Many problems that are hard on general graphs become solvable on chordal graphs. The random generation of instances of chordal graphs for testing these algorithms is often required. Nevertheless, there are only few known algorithms that generate random chordal graphs, and, as far as we know, none of them generate chordal graphs uniformly at random (where each chordal graph appears with equal probability). In this paper we propose a Markov chain Monte Carlo (MCMC) method to sample connected chordal graphs uniformly at random. Additionally, we propose a Markov chain that generates connected chordal graphs with a bounded treewidth uniformly at random. Bounding the treewidth parameter (which bounds the largest clique) has direct implications on the running time of various algorithms on chordal graphs. For each of the proposed Markov chains we prove that they are ergodic and therefore converge to the uniform distribution. Finally, as initial evidence that the Markov chains have the potential to mix rapidly, we prove that the chain on graphs with bounded treewidth mixes rapidly for trees (chordal graphs with treewidth bound of one).

APA, Harvard, Vancouver, ISO, and other styles

9

McKee, Terry A. "Symmetric graph-theoretic roles of two-pairs and chords of cycles." Discrete Mathematics, Algorithms and Applications 06, no. 03 (June 16, 2014): 1450031. http://dx.doi.org/10.1142/s1793830914500311.

Full text

Abstract:

Although the notion of a two-pair (a pair of vertices between which all induced paths have length 2) was invented for the class of weakly chordal graphs, two-pairs can also play a fundamental role for smaller graph classes. Indeed, two-pairs and chords of cycles can collaborate symmetrically to give parallel characterizations of weakly chordal, chordal, and strongly chordal graphs (and of distance-hereditary graphs).

APA, Harvard, Vancouver, ISO, and other styles

10

TALMACIU, MIHAI. "On Hyper-Chordal graphs." Carpathian Journal of Mathematics 37, no. 1 (February 5, 2021): 119–26. http://dx.doi.org/10.37193/cjm.2021.01.12.

Full text

Abstract:

Triangulated graphs have many interesting properties (perfection, recognition algorithms, combinatorial optimization algorithms with linear complexity). Hyper-triangulated graphs are those where each induced subgraph has a hyper-simplicial vertex. In this paper we give the characterizations of hyper-triangulated graphs using an ordering of vertices and the weak decomposition. We also offer a recognition algorithm for the hyper-triangulated graphs, the inclusions between the triangulated graphs generalizations and we show that any hyper-triangulated graph is perfect.

APA, Harvard, Vancouver, ISO, and other styles

11

Nagarathinam, R., N. Parvathi, and . "Grundy Number of Some Chordal Graphs." International Journal of Engineering & Technology 7, no. 4.10 (October 2, 2018): 64. http://dx.doi.org/10.14419/ijet.v7i4.10.20708.

Full text

Abstract:

For a given graph G and integer k, the Coloring problem is that of testing whether G has a k-coloring, that is, whether there exists a vertex mapping c : V → {1, 2, . . .} such that c(u) 12â‰ "> c(v) for every edge uv ∈ E. For proper coloring, colors assigned must be minimum, but for Grundy coloring which should be maximum. In this instance, Grundy numbers of chordal graphs like Cartesian product of two path graphs, join of the path and complete graphs and the line graph of tadpole have been executed

APA, Harvard, Vancouver, ISO, and other styles

12

Ibarra, Louis. "The clique-separator graph for chordal graphs." Discrete Applied Mathematics 157, no. 8 (April 2009): 1737–49. http://dx.doi.org/10.1016/j.dam.2009.02.006.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Nikolopoulos, Stavros D., and Leonidas Palios. "Parallel Algorithms for Recognizing P5-free and ${\bar P}_5$-free Weakly Chordal Graphs." Parallel Processing Letters 14, no. 01 (March 2004): 119–29. http://dx.doi.org/10.1142/s0129626404001763.

Full text

Abstract:

We prove algorithmic characterizations of weakly chordal graphs, which lead to efficient parallel algorithms for recognizing P5-free and [Formula: see text]-free weakly chordal graphs. For an input graph on n vertices and m edges, our algorithms run in O( log 2n) time and require O(m2/ log n) processors on the EREW PRAM model of computation. The proposed recognition algorithms efficiently detect P5 s and [Formula: see text] in weakly chordal graphs in O( log n) time with O(m2/ log n) processors on the EREW PRAM. Additionally, we show how the algorithms can be augmented to provide a certificate for the existence of a P5 (or a [Formula: see text]) in case the input graph is not P5-free (respectively, [Formula: see text]-free) weakly chordal.

APA, Harvard, Vancouver, ISO, and other styles

14

McKee, Terry A. "Strengthening strongly chordal graphs." Discrete Mathematics, Algorithms and Applications 08, no. 01 (February 26, 2016): 1650002. http://dx.doi.org/10.1142/s1793830916500026.

Full text

Abstract:

An [Formula: see text]-chord of a cycle [Formula: see text] is a chord that forms a new cycle with a length-[Formula: see text] subpath of [Formula: see text] when [Formula: see text] is at most half the length of [Formula: see text]. Define a graph to be [Formula: see text]-strongly chordal if, for every [Formula: see text], every cycle long enough to have an [Formula: see text]-chord always has an [Formula: see text]-chord. The [Formula: see text]-strongly chordal and [Formula: see text]-strongly chordal graphs are, respectively, the chordal and strongly chordal graphs. Several characterizations of [Formula: see text]-strongly chordal graphs are proved, along with details of the class of [Formula: see text]-strongly chordal graphs.

APA, Harvard, Vancouver, ISO, and other styles

15

Agnarsson, Geir. "On chordal graphs and their chromatic polynomials." MATHEMATICA SCANDINAVICA 93, no. 2 (December 1, 2003): 240. http://dx.doi.org/10.7146/math.scand.a-14421.

Full text

Abstract:

We derive a formula for the chromatic polynomial of a chordal or a triangulated graph in terms of its maximal cliques. As a corollary we obtain a way to write down an explicit formula for the chromatic polynomial for an arbitrary power of a graph which belongs to any given class of chordal graphs that are closed under taking powers.

APA, Harvard, Vancouver, ISO, and other styles

16

Emtander, Eric. "A class of hypergraphs that generalizes chordal graphs." MATHEMATICA SCANDINAVICA 106, no. 1 (March 1, 2010): 50. http://dx.doi.org/10.7146/math.scand.a-15124.

Full text

Abstract:

In this paper we introduce a class of hypergraphs that we call chordal. We also extend the definition of triangulated hypergraphs, given by H. T. Hà and A. Van Tuyl, so that a triangulated hypergraph, according to our definition, is a natural generalization of a chordal (rigid circuit) graph. R. Fröberg has showed that the chordal graphs corresponds to graph algebras, $R/I(\mathcal{G})$, with linear resolutions. We extend Fröberg's method and show that the hypergraph algebras of generalized chordal hypergraphs, a class of hypergraphs that includes the chordal hypergraphs, have linear resolutions. The definitions we give, yield a natural higher dimensional version of the well known flag property of simplicial complexes. We obtain what we call $d$-flag complexes.

APA, Harvard, Vancouver, ISO, and other styles

17

PRADHAN, D. "COMPLEXITY OF CERTAIN FUNCTIONAL VARIANTS OF TOTAL DOMINATION IN CHORDAL BIPARTITE GRAPHS." Discrete Mathematics, Algorithms and Applications 04, no. 03 (August 6, 2012): 1250045. http://dx.doi.org/10.1142/s1793830912500450.

Full text

Abstract:

In this paper, we consider minimum total domination problem along with two of its variations namely, minimum signed total domination problem and minimum minus total domination problem for chordal bipartite graphs. In the minimum total domination problem, the objective is to find a smallest size subset TD ⊆ V of a given graph G = (V, E) such that |TD∩NG(v)| ≥ 1 for every v ∈ V. In the minimum signed (minus) total domination problem for a graph G = (V, E), it is required to find a function f : V → {-1, 1} ({-1, 0, 1}) such that f(NG(v)) = ∑u∈NG(v)f(u) ≥ 1 for each v ∈ V, and the cost f(V) = ∑v∈V f(v) is minimized. We first show that for a given chordal bipartite graph G = (V, E) with a weak elimination ordering, a minimum total dominating set can be computed in O(n + m) time, where n = |V| and m = |E|. This improves the complexity of the minimum total domination problem for chordal bipartite graphs from O(n2) time to O(n + m) time. We then adopt a unified approach to solve the minimum signed (minus) total domination problem for chordal bipartite graphs in O(n + m) time. The method is also able to solve the minimum k-tuple total domination problem for chordal bipartite graphs in O(n + m) time. For a fixed integer k ≥ 1 and a graph G = (V, E), the minimum k-tuple total domination problem is to find a smallest subset TDk ⊆ V such that |TDk ∩ NG(v)| ≥ k for every v ∈ V.

APA, Harvard, Vancouver, ISO, and other styles

18

Scheidweiler, Robert, and Sebastian Wiederrecht. "On chordal graph and line graph squares." Discrete Applied Mathematics 243 (July 2018): 239–47. http://dx.doi.org/10.1016/j.dam.2018.02.013.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Argiroffo, Gabriela, Valeria Leoni, and Pablo Torres. "-domination for chordal graphs and related graph classes." Electronic Notes in Discrete Mathematics 44 (November 2013): 219–24. http://dx.doi.org/10.1016/j.endm.2013.10.034.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Tang, C. Y., M. T. Ko, C. W. Ho, T. s. Hsu, and S. L. Peng. "Graph Searching on Some Subclasses of Chordal Graphs." Algorithmica 27, no. 3 (June 1, 2000): 395–426. http://dx.doi.org/10.1007/s004530010026.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Panda, B. S., and D. Pradhan. "A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs." Discrete Mathematics, Algorithms and Applications 07, no. 02 (May 25, 2015): 1550020. http://dx.doi.org/10.1142/s1793830915500202.

Full text

Abstract:

A set D ⊆ V is a restrained dominating set of a graph G = (V, E) if every vertex in V\D is adjacent to a vertex in D and a vertex in V\D. Given a graph G and a positive integer k, the restrained domination problem is to check whether G has a restrained dominating set of size at most k. The restrained domination problem is known to be NP-complete even for chordal graphs. In this paper, we propose a linear time algorithm to compute a minimum restrained dominating set of a proper interval graph. We present a polynomial time reduction that proves the NP-completeness of the restrained domination problem for undirected path graphs, chordal bipartite graphs, circle graphs, and planar graphs.

APA, Harvard, Vancouver, ISO, and other styles

22

Takaoka, Asahi. "Complexity of Hamiltonian Cycle Reconfiguration." Algorithms 11, no. 9 (September 17, 2018): 140. http://dx.doi.org/10.3390/a11090140.

Full text

Abstract:

The Hamiltonian cycle reconfiguration problem asks, given two Hamiltonian cycles C 0 and C t of a graph G, whether there is a sequence of Hamiltonian cycles C 0 , C 1 , … , C t such that C i can be obtained from C i − 1 by a switch for each i with 1 ≤ i ≤ t , where a switch is the replacement of a pair of edges u v and w z on a Hamiltonian cycle with the edges u w and v z of G, given that u w and v z did not appear on the cycle. We show that the Hamiltonian cycle reconfiguration problem is PSPACE-complete, settling an open question posed by Ito et al. (2011) and van den Heuvel (2013). More precisely, we show that the Hamiltonian cycle reconfiguration problem is PSPACE-complete for chordal bipartite graphs, strongly chordal split graphs, and bipartite graphs with maximum degree 6. Bipartite permutation graphs form a proper subclass of chordal bipartite graphs, and unit interval graphs form a proper subclass of strongly chordal graphs. On the positive side, we show that, for any two Hamiltonian cycles of a bipartite permutation graph and a unit interval graph, there is a sequence of switches transforming one cycle to the other, and such a sequence can be obtained in linear time.

APA, Harvard, Vancouver, ISO, and other styles

23

Guo, Jin, Yi-Huang Shen, and Tongsuo Wu. "Edgewise strongly shellable clutters." Journal of Algebra and Its Applications 17, no. 01 (January 2018): 1850018. http://dx.doi.org/10.1142/s0219498818500184.

Full text

Abstract:

When [Formula: see text] is a chordal clutter in the sense of Woodroofe or Emtander, we show that the complement clutter is edgewise strongly shellable. When [Formula: see text] is indeed a finite simple graph, we provide additional characterization of chordal graphs from the point of view of strong shellability. In particular, the generic graph [Formula: see text] of a tree is shown to be bi-strongly shellable.

APA, Harvard, Vancouver, ISO, and other styles

24

SHERMAN, DAVID, MING TSAI, CHENG-KUAN LIN, LÁSZLÓ LIPTÁK, EDDIE CHENG, JIMMY J. M. TAN, and LIH-HSING HSU. "4-ORDERED HAMILTONICITY FOR SOME CHORDAL RING GRAPHS." Journal of Interconnection Networks 11, no. 03n04 (September 2010): 157–74. http://dx.doi.org/10.1142/s0219265910002787.

Full text

Abstract:

A graph G is k-ordered if for any sequence of k distinct vertices of G, there exists a cycle in G containing these k vertices in the specified order. It is k-ordered Hamiltonian if, in addition, the required cycle is Hamiltonian. The question of the existence of an infinite class of 3-regular 4-ordered Hamiltonian graphs was posed in 1997 by Ng and Schultz.13At the time, the only known examples were K4and K3,3. Some progress was made in 2008 by Mészáros,12when the Peterson graph was found to be 4-ordered and the Heawood graph was proved to be 4-ordered Hamiltonian; moreover, an infinite class of 3-regular 4-ordered graphs was found. In 2010 a subclass of generalized Petersen graphs was shown to be 4-ordered by Hsu et al.,10with an infinite subset of this subclass being 4-ordered Hamiltonian, thus answering the open question. In this paper we find another infinite class of 3-regular 4-ordered Hamiltonian graphs, part of a subclass of the chordal ring graphs. In addition, we classify precisely which of these graphs are 4-ordered Hamiltonian.

APA, Harvard, Vancouver, ISO, and other styles

25

NARAYANASWAMY, N. S., and N. SADAGOPAN. "A UNIFIED FRAMEWORK FOR BI(TRI)CONNECTIVITY AND CHORDAL AUGMENTATION." International Journal of Foundations of Computer Science 24, no. 01 (January 2013): 67–93. http://dx.doi.org/10.1142/s0129054113400054.

Full text

Abstract:

For a connected non-complete graph, a vertex separator is a subset of vertices whose deletion increases the number of connected components and the vertex connectivity of the graph refers to the size of a minimum vertex separator. A graph with the vertex connectivity k is said to be k-vertex connected. Given a k-vertex connected graph G, vertex connectivity augmentation determines a smallest set of edges whose augmentation to G makes it (k + 1)-vertex connected. In this paper, we report our study on connectivity augmentation in 1-connected graphs, 2-connected graphs, and k-connected chordal graphs. We first represent the graph under consideration using a "tree-like" graph. This tree is unique and explicitly captures the connectivity information of the graph. Using this tree, our proposed data structure maintains the set of equivalence classes based on an equivalence relation on the set of leaves of the tree. This partition determines a set of edges to be augmented to increase the connectivity of the graph by one. Based on our data structure, we present a new combinatorial analysis and an elegant proof of correctness of our linear-time algorithm for an optimum connectivity augmentation. The novelty is in the data structure which is a unified framework for all three augmentations. As far as the run-time analysis is concerned, given the associated tree, our approach yields an augmentation set in linear time.

APA, Harvard, Vancouver, ISO, and other styles

26

Fomin, Fedor V., and Petr A. Golovach. "Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs." Algorithmica 83, no. 7 (April 11, 2021): 2170–214. http://dx.doi.org/10.1007/s00453-021-00822-x.

Full text

Abstract:

AbstractWe study algorithmic properties of the graph class $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e , that is, graphs that can be turned into a chordal graph by adding at most k edges or, equivalently, the class of graphs of fill-in at most k. It appears that a number of fundamental intractable optimization problems being parameterized by k admit subexponential algorithms on graphs from $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e . More precisely, we identify a large class of optimization problems on $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e solvable in time $$2^{{\mathcal{O}}(\sqrt{k}\log k)}\cdot n^{{\mathcal{O}}(1)}$$ 2 O ( k log k ) · n O ( 1 ) . Examples of the problems from this class are finding an independent set of maximum weight, finding a feedback vertex set or an odd cycle transversal of minimum weight, or the problem of finding a maximum induced planar subgraph. On the other hand, we show that for some fundamental optimization problems, like finding an optimal graph coloring or finding a maximum clique, are FPT on $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e when parameterized by k but do not admit subexponential in k algorithms unless ETH fails. Besides subexponential time algorithms, the class of $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e graphs appears to be appealing from the perspective of kernelization (with parameter k). While it is possible to show that most of the weighted variants of optimization problems do not admit polynomial in k kernels on $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e graphs, this does not exclude the existence of Turing kernelization and kernelization for unweighted graphs. In particular, we construct a polynomial Turing kernel for Weighted Clique on $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e graphs. For (unweighted) Independent Set we design polynomial kernels on two interesting subclasses of $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e , namely, $${\textsc {Interval}}{-ke}$$ I N T E R V A L - k e and $${\textsc {Split}}{-ke}$$ S P L I T - k e graphs.

APA, Harvard, Vancouver, ISO, and other styles

27

PANDA, B. S., VIJAY NATARAJAN, and SAJAL K. DAS. "PARALLEL ALGORITHMS FOR HAMILTONIAN 2-SEPARATOR CHORDAL GRAPHS." Parallel Processing Letters 12, no. 01 (March 2002): 51–64. http://dx.doi.org/10.1142/s0129626402000823.

Full text

Abstract:

In this paper we propose a parallel algorithm to construct a one-sided monotone polygon from a Hamiltonian 2-separator chordal graph. The algorithm requires O( log n) time and O(n) processors on the CREW PRAM model, where n is the number of vertices and m is the number of edges in the graph. We also propose parallel algorithms to recognize Hamiltonian 2-separator chordal graphs and to construct a Hamiltonian cycle in such a graph. They run in O( log 2 n) time using O(mn) processors on the CRCW PRAM model and O( log 2 n) time using O(m) processors on the CREW PRAM model, respectively.

APA, Harvard, Vancouver, ISO, and other styles

28

Jose, Bibin K. "Some New Classes of Open Distance-Pattern Uniform Graphs." International Journal of Combinatorics 2013 (July 24, 2013): 1–7. http://dx.doi.org/10.1155/2013/863439.

Full text

Abstract:

Given an arbitrary nonempty subset M of vertices in a graph G=(V,E), each vertex u in G is associated with the set fMo(u)={d(u,v):v∈M,u≠v} and called its open M-distance-pattern. The graph G is called open distance-pattern uniform (odpu-) graph if there exists a subset M of V(G) such that fMo(u)=fMo(v) for all u,v∈V(G), and M is called an open distance-pattern uniform (odpu-) set of G. The minimum cardinality of an odpu-set in G, if it exists, is called the odpu-number of G and is denoted by od(G). Given some property P, we establish characterization of odpu-graph with property P. In this paper, we characterize odpu-chordal graphs, and thereby characterize interval graphs, split graphs, strongly chordal graphs, maximal outerplanar graphs, and ptolemaic graphs that are odpu-graphs. We also characterize odpu-self-complementary graphs, odpu-distance-hereditary graphs, and odpu-cographs. We prove that the odpu-number of cographs is even and establish that any graph G can be embedded into a self-complementary odpu-graph H, such that G and G¯ are induced subgraphs of H. We also prove that the odpu-number of a maximal outerplanar graph is either 2 or 5.

APA, Harvard, Vancouver, ISO, and other styles

29

Erdős, Paul, Edward T. Ordman, and Yechezkel Zalcstein. "Clique Partitions of Chordal Graphs." Combinatorics, Probability and Computing 2, no. 4 (December 1993): 409–15. http://dx.doi.org/10.1017/s0963548300000808.

Full text

Abstract:

To partition the edges of a chordal graph on n vertices into cliques may require as many as n2/6 cliques; there is an example requiring this many, which is also a threshold graph and a split graph. It is unknown whether this many cliques will always suffice. We are able to show that (1 − c)n2/4 cliques will suffice for some c > 0.

APA, Harvard, Vancouver, ISO, and other styles

30

Feghali, Carl, and Jiří Fiala. "Reconfiguration graph for vertex colourings of weakly chordal graphs." Discrete Mathematics 343, no. 3 (March 2020): 111733. http://dx.doi.org/10.1016/j.disc.2019.111733.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

DOHMEN, KLAUS. "Bonferroni-Type Inequalities via Chordal Graphs." Combinatorics, Probability and Computing 11, no. 4 (July 2002): 349–51. http://dx.doi.org/10.1017/s0963548302005151.

Full text

Abstract:

Let {Av}v∈V be a finite collection of events and G = (V, E) be a chordal graph. Our main result – the chordal graph sieve – is a Bonferroni-type inequality where the selection of intersections in the estimates is determined by a chordal graph G. It interpolates between Boole's inequality (G empty) and the sieve formula (G complete). By varying G, several inequalities both well-known and new are obtained in a concise and unified way.

APA, Harvard, Vancouver, ISO, and other styles

32

Ekim, Tınaz, Mordechai Shalom, and Oylum Şeker. "The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation." Journal of Combinatorial Optimization 41, no. 3 (February 26, 2021): 710–35. http://dx.doi.org/10.1007/s10878-021-00712-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Lin, In-Jen, Terry A. McKee, and D. B. West. "The leafage of a chordal graph." Discussiones Mathematicae Graph Theory 18, no. 1 (1998): 23. http://dx.doi.org/10.7151/dmgt.1061.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Khamis, H. J., and T. A. McKee. "Chordal Graph Models of Contingency Tables." Computers & Mathematics with Applications 34, no. 11 (December 1997): 89–97. http://dx.doi.org/10.1016/s0898-1221(97)00222-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Harary, Frank, and Terry A. McKee. "The square of a chordal graph." Discrete Mathematics 128, no. 1-3 (April 1994): 165–72. http://dx.doi.org/10.1016/0012-365x(94)90110-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Edenbrandt, Anders. "Chordal graph recognition is in NC." Information Processing Letters 24, no. 4 (March 1987): 239–41. http://dx.doi.org/10.1016/0020-0190(87)90140-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Studený, Milan, James Cussens, and Václav Kratochvíl. "The dual polyhedron to the chordal graph polytope and the rebuttal of the chordal graph conjecture." International Journal of Approximate Reasoning 138 (November 2021): 188–203. http://dx.doi.org/10.1016/j.ijar.2021.07.014.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Alkam, Osama, and Emad Abu Osba. "Zero Divisor Graph for the Ring of Eisenstein Integers Modulo n." Algebra 2014 (December 15, 2014): 1–6. http://dx.doi.org/10.1155/2014/146873.

Full text

Abstract:

Let En be the ring of Eisenstein integers modulo n. In this paper we study the zero divisor graph Γ(En). We find the diameters and girths for such zero divisor graphs and characterize n for which the graph Γ(En) is complete, complete bipartite, bipartite, regular, Eulerian, Hamiltonian, or chordal.

APA, Harvard, Vancouver, ISO, and other styles

39

Rahman, Md Zamilur, Asish Mukhopadhyay, and Yash P. Aneja. "A separator-based method for generating weakly chordal graphs." Discrete Mathematics, Algorithms and Applications 12, no. 04 (July 23, 2020): 2050039. http://dx.doi.org/10.1142/s1793830920500391.

Full text

Abstract:

We propose a scheme for generating a weakly chordal graph on [Formula: see text] vertices with [Formula: see text] edges. In this method, we first construct a tree and then generate an orthogonal layout (which is a weakly chordal graph on the [Formula: see text] vertices) based on this tree. We then insert additional edges, if needed, for a total of [Formula: see text] edges. Our algorithm ensures that the graph remains weakly chordal after each edge is inserted. The time complexity of an insertion query is [Formula: see text], where [Formula: see text] and [Formula: see text] are the degrees of the vertices [Formula: see text] and [Formula: see text] we want to join with an edge and an insertion takes constant time. The advantages of this method are that it uses very simple data structures and exploits the basic structural properties of a weakly chordal graph.

APA, Harvard, Vancouver, ISO, and other styles

40

Lee, Chuan-Min. "Weighted Maximum-Clique Transversal Sets of Graphs." ISRN Discrete Mathematics 2011 (January 26, 2011): 1–20. http://dx.doi.org/10.5402/2011/540834.

Full text

Abstract:

A maximum-clique transversal set of a graph G is a subset of vertices intersecting all maximum cliques of G. The maximum-clique transversal set problem is to find a maximum-clique transversal set of G of minimum cardinality. Motivated by the placement of transmitters for cellular telephones, Chang, Kloks, and Lee introduced the concept of maximum-clique transversal sets on graphs in 2001. In this paper, we study the weighted version of the maximum-clique transversal set problem for split graphs, balanced graphs, strongly chordal graph, Helly circular-arc graphs, comparability graphs, distance-hereditary graphs, and graphs of bounded treewidth.

APA, Harvard, Vancouver, ISO, and other styles

41

Pal, Saikat, and D. Pradhan. "The strong domination problem in block graphs and proper interval graphs." Discrete Mathematics, Algorithms and Applications 11, no. 06 (December 2019): 1950063. http://dx.doi.org/10.1142/s1793830919500630.

Full text

Abstract:

In a graph [Formula: see text], the degree of a vertex [Formula: see text], denoted by [Formula: see text], is defined as the number of edges incident on [Formula: see text]. A set [Formula: see text] of vertices of [Formula: see text] is called a strong dominating set if for every [Formula: see text], there exists a vertex [Formula: see text] such that [Formula: see text] and [Formula: see text]. For a given graph [Formula: see text], Min-Strong-DS is the problem of finding a strong dominating set of minimum cardinality. The decision version of Min-Strong-DS is shown to be NP -complete for chordal graphs. In this paper, we present polynomial time algorithms for computing a strong dominating set in block graphs and proper interval graphs, two subclasses of chordal graphs. On the other hand, we show that for a graph [Formula: see text] with [Formula: see text]-vertices, Min-Strong-DS cannot be approximated within a factor of [Formula: see text] for every [Formula: see text], unless NP [Formula: see text] DTIME ([Formula: see text]). We also show that Min-Strong-DS is APX -complete for graphs with maximum degree [Formula: see text]. On the positive side, we show that Min-Strong-DS can be approximated within a factor of [Formula: see text] for graphs with maximum degree [Formula: see text].

APA, Harvard, Vancouver, ISO, and other styles

42

Gunda, Spoorthy, Pallavi Jain, Daniel Lokshtanov, Saket Saurabh, and Prafullkumar Tale. "On the Parameterized Approximability of Contraction to Classes of Chordal Graphs." ACM Transactions on Computation Theory 13, no. 4 (December 31, 2021): 1–40. http://dx.doi.org/10.1145/3470869.

Full text

Abstract:

A graph operation that contracts edges is one of the fundamental operations in the theory of graph minors. Parameterized Complexity of editing to a family of graphs by contracting k edges has recently gained substantial scientific attention, and several new results have been obtained. Some important families of graphs, namely, the subfamilies of chordal graphs, in the context of edge contractions, have proven to be significantly difficult than one might expect. In this article, we study the F -Contraction problem, where F is a subfamily of chordal graphs, in the realm of parameterized approximation. Formally, given a graph G and an integer k , F -Contraction asks whether there exists X ⊆ E(G) such that G/X ∈ F and | X | ≤ k . Here, G/X is the graph obtained from G by contracting edges in X . We obtain the following results for the F - Contraction problem: • Clique Contraction is known to be FPT . However, unless NP⊆ coNP/ poly , it does not admit a polynomial kernel. We show that it admits a polynomial-size approximate kernelization scheme ( PSAKS ). That is, it admits a (1 + ε)-approximate kernel with O ( k f(ε)) vertices for every ε > 0. • Split Contraction is known to be W[1]-Hard . We deconstruct this intractability result in two ways. First, we give a (2+ε)-approximate polynomial kernel for Split Contraction (which also implies a factor (2+ε)- FPT -approximation algorithm for Split Contraction ). Furthermore, we show that, assuming Gap-ETH , there is no (5/4-δ)- FPT -approximation algorithm for Split Contraction . Here, ε, δ > 0 are fixed constants. • Chordal Contraction is known to be W[2]-Hard . We complement this result by observing that the existing W[2]-hardness reduction can be adapted to show that, assuming FPT ≠ W[1] , there is no F(k) - FPT -approximation algorithm for Chordal Contraction . Here, F(k) is an arbitrary function depending on k alone. We say that an algorithm is an h(k) - FPT -approximation algorithm for the F -Contraction problem, if it runs in FPT time, and on any input (G, k) such that there exists X ⊆ E(G) satisfying G/X ∈ F and | X | ≤ k , it outputs an edge set Y of size at most h(k) ċ k for which G/Y is in F .

APA, Harvard, Vancouver, ISO, and other styles

43

Lin, Chih-Yuan, Jia-Jie Liu, Yue-Li Wang, William Chung-Kung Yen, and Chiun-Chieh Hsu. "The Outer-Paired Domination of Graphs." International Journal of Foundations of Computer Science 33, no. 02 (February 2022): 141–48. http://dx.doi.org/10.1142/s0129054122500034.

Full text

Abstract:

In this paper, we introduce a new variant of domination called the outer-paired domination. For a graph [Formula: see text], an outer-paired dominating set [Formula: see text] is a dominating set of [Formula: see text] such that the induced subgraph of [Formula: see text] contains a perfect matching. The outer-paired domination number of a graph [Formula: see text] is the cardinality of a minimum outer-paired dominating set of [Formula: see text]. We show that finding the outer-paired domination number of a graph [Formula: see text] is NP-hard on bipartite graphs, chordal graphs, and planar graphs. We also propose a linear-time algorithm for solving the outer-paired domination problem on trees.

APA, Harvard, Vancouver, ISO, and other styles

44

GEBAUER, HEIDI, and YOSHIO OKAMOTO. "FAST EXPONENTIAL-TIME ALGORITHMS FOR THE FOREST COUNTING AND THE TUTTE POLYNOMIAL COMPUTATION IN GRAPH CLASSES." International Journal of Foundations of Computer Science 20, no. 01 (February 2009): 25–44. http://dx.doi.org/10.1142/s0129054109006437.

Full text

Abstract:

We prove # P -completeness for counting the number of forests in regular graphs and chordal graphs. We also present algorithms for this problem, running in O *(1.8494m) time for 3-regular graphs, and O *(1.9706m) time for unit interval graphs, where m is the number of edges in the graph and O *-notation ignores a polynomial factor. The algorithms can be generalized to the Tutte polynomial computation.

APA, Harvard, Vancouver, ISO, and other styles

45

Kamath, S. S., A. Senthil Thilak, and M. Rashmi. "Algorithmic aspects of k-part degree restricted domination in graphs." Discrete Mathematics, Algorithms and Applications 12, no. 05 (July 7, 2020): 2050057. http://dx.doi.org/10.1142/s1793830920500573.

Full text

Abstract:

The concept of network is predominantly used in several applications of computer communication networks. It is also a fact that the dominating set acts as a virtual backbone in a communication network. These networks are vulnerable to breakdown due to various causes, including traffic congestion. In such an environment, it is necessary to regulate the traffic so that these vulnerabilities could be reasonably controlled. Motivated by this, [Formula: see text]-part degree restricted domination is defined as follows. For a positive integer [Formula: see text], a dominating set [Formula: see text] of a graph [Formula: see text] is said to be a [Formula: see text]-part degree restricted dominating set ([Formula: see text]-DRD set) if for all [Formula: see text], there exists a set [Formula: see text] such that [Formula: see text] and [Formula: see text]. The minimum cardinality of a [Formula: see text]-DRD set of a graph [Formula: see text] is called the [Formula: see text]-part degree restricted domination number of [Formula: see text] and is denoted by [Formula: see text]. In this paper, we present a polynomial time reduction that proves the NP -completeness of the [Formula: see text]-part degree restricted domination problem for bipartite graphs, chordal graphs, undirected path graphs, chordal bipartite graphs, circle graphs, planar graphs and split graphs. We propose a polynomial time algorithm to compute a minimum [Formula: see text]-DRD set of a tree and minimal [Formula: see text]-DRD set of a graph.

APA, Harvard, Vancouver, ISO, and other styles

46

Bakonyi, Mihály. "On Gaussian elimination and determinant formulas for matrices with chordal inverses." Bulletin of the Australian Mathematical Society 46, no. 3 (December 1992): 435–40. http://dx.doi.org/10.1017/s0004972700012090.

Full text

Abstract:

In this paper a formula is obtained for the entries of the diagonal factor in the U D L factorisation of an invertible operator matrix in the case when its inverse has a chordal graph. As a consequence, in the finite dimensional case a determinant formula is obtained in terms of some key principal minors. After a cancellation process this formula leads to a determinant formula from an earlier paper by W.W. Barrett and C.R. Johnson, deriving in this way a different and shorter proof of their result. Finally, an algorithmic method of constructing minimal vertex separators of chordal graphs is presented.

APA, Harvard, Vancouver, ISO, and other styles

47

Planken, L. R., M. M. De Weerdt, and R. P. J. Van der Krogt. "Computing All-Pairs Shortest Paths by Leveraging Low Treewidth." Journal of Artificial Intelligence Research 43 (March 19, 2012): 353–88. http://dx.doi.org/10.1613/jair.3509.

Full text

Abstract:

We present two new and efficient algorithms for computing all-pairs shortest paths. The algorithms operate on directed graphs with real (possibly negative) weights. They make use of directed path consistency along a vertex ordering d. Both algorithms run in O(n^2 w_d) time, where w_d is the graph width induced by this vertex ordering. For graphs of constant treewidth, this yields O(n^2) time, which is optimal. On chordal graphs, the algorithms run in O(nm) time. In addition, we present a variant that exploits graph separators to arrive at a run time of O(n w_d^2 + n^2 s_d) on general graphs, where s_d

APA, Harvard, Vancouver, ISO, and other styles

48

Parra, Andreas, and Petra Scheffler. "Characterizations and algorithmic applications of chordal graph embeddings." Discrete Applied Mathematics 79, no. 1-3 (November 1997): 171–88. http://dx.doi.org/10.1016/s0166-218x(97)00041-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Guo, Xijuan, Huiping Yao, and Fang Cheng. "Inverse M-matrices completions of then-chordal graph." International Journal of Computer Mathematics 82, no. 3 (March 2005): 275–88. http://dx.doi.org/10.1080/00207160412331290694.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Scheinerman, Edward R. "On the interval number of a chordal graph." Journal of Graph Theory 12, no. 3 (1988): 311–16. http://dx.doi.org/10.1002/jgt.3190120303.

Full text

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!