Log in

Relevant bibliographies by topics / K-chordal Graphs

Contents

Journal articles
Dissertations / Theses
Book chapters
Conference papers

Academic literature on the topic 'K-chordal Graphs'

Author: Grafiati

Published: 4 June 2021

Last updated: 6 September 2023

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

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'K-chordal Graphs.'

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.

Journal articles on the topic "K-chordal Graphs"

1

Fomin, Fedor V., and Petr A. Golovach. "Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs." Algorithmica 83, no. 7 (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{

APA, Harvard, Vancouver, ISO, and other styles

2

Lee, Chuan-Min. "Algorithmic Aspects of Some Variations of Clique Transversal and Clique Independent Sets on Graphs." Algorithms 14, no. 1 (2021): 22. http://dx.doi.org/10.3390/a14010022.

Full text

Abstract:

This paper studies the maximum-clique independence problem and some variations of the clique transversal problem such as the {k}-clique, maximum-clique, minus clique, signed clique, and k-fold clique transversal problems from algorithmic aspects for k-trees, suns, planar graphs, doubly chordal graphs, clique perfect graphs, total graphs, split graphs, line graphs, and dually chordal graphs. We give equations to compute the {k}-clique, minus clique, signed clique, and k-fold clique transversal numbers for suns, and show that the {k}-clique transversal problem is polynomial-time solvable for gra

APA, Harvard, Vancouver, ISO, and other styles

3

PRADHAN, D. "COMPLEXITY OF CERTAIN FUNCTIONAL VARIANTS OF TOTAL DOMINATION IN CHORDAL BIPARTITE GRAPHS." Discrete Mathematics, Algorithms and Applications 04, no. 03 (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

APA, Harvard, Vancouver, ISO, and other styles

4

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 (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 pr

APA, Harvard, Vancouver, ISO, and other styles

5

Nagarathinam, R., N. Parvathi, and . "Grundy Number of Some Chordal Graphs." International Journal of Engineering & Technology 7, no. 4.10 (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

6

McKee, Terry A. "Characterizing k-chordal unichord-free graphs." Discrete Mathematics, Algorithms and Applications 10, no. 04 (2018): 1850043. http://dx.doi.org/10.1142/s179383091850043x.

Full text

Abstract:

The [Formula: see text]-chordal graphs, defined by no induced cycle having length greater than [Formula: see text], generalize the traditional chordal graphs (where [Formula: see text]), which Dirac characterized in 1961 by minimal separators always inducing complete subgraphs. The more recent unichord-free graphs, defined by no cycle having a unique chord, have been characterized by minimal separators always inducing edgeless subgraphs. This sharp contrast of minimal separators motivates a new concept of [Formula: see text]-unichord-free graphs, strengthening the unichord-free graphs (where [

APA, Harvard, Vancouver, ISO, and other styles

7

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 (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 approxim

APA, Harvard, Vancouver, ISO, and other styles

8

SHERMAN, DAVID, MING TSAI, CHENG-KUAN LIN, et al. "4-ORDERED HAMILTONICITY FOR SOME CHORDAL RING GRAPHS." Journal of Interconnection Networks 11, no. 03n04 (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

APA, Harvard, Vancouver, ISO, and other styles

9

Markenzon, Lilian, Paulo Renato da Costa Pereira, and Christina F. E. M. Waga. "k-separator chordal graphs: leafage and subfamilies." International Transactions in Operational Research 20, no. 5 (2012): 681–88. http://dx.doi.org/10.1111/j.1475-3995.2012.00875.x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Goodarzi, Afshin. "Clique vectors of k-connected chordal graphs." Journal of Combinatorial Theory, Series A 132 (May 2015): 188–93. http://dx.doi.org/10.1016/j.jcta.2015.01.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic "K-chordal Graphs"

1

Mathew, Rogers. "Boxicity And Cubicity : A Study On Special Classes Of Graphs." Thesis, 2012. https://etd.iisc.ac.in/handle/2005/2320.

Full text

Abstract:

Let F be a family of sets. A graph G is an intersection graph of sets from the family F if there exists a mapping f : V (G)→ F such that, An interval graph is an intersection graph of a family of closed intervals on the real line. Interval graphs find application in diverse fields ranging from DNA analysis to VLSI design. An interval on the real line can be generalized to a k dimensional box or k-box. A k-box B = (R1.R2….Rk) is defined to be the Cartesian product R1 × R2 × …× Rk, where each Ri is a closed interval on the real line. If each Ri is a unit length interval, we call B a k-cube. T

APA, Harvard, Vancouver, ISO, and other styles

2

Mathew, Rogers. "Boxicity And Cubicity : A Study On Special Classes Of Graphs." Thesis, 2012. http://etd.iisc.ernet.in/handle/2005/2320.

Full text

Abstract:

Let F be a family of sets. A graph G is an intersection graph of sets from the family F if there exists a mapping f : V (G)→ F such that, An interval graph is an intersection graph of a family of closed intervals on the real line. Interval graphs find application in diverse fields ranging from DNA analysis to VLSI design. An interval on the real line can be generalized to a k dimensional box or k-box. A k-box B = (R1.R2….Rk) is defined to be the Cartesian product R1 × R2 × …× Rk, where each Ri is a closed interval on the real line. If each Ri is a unit length interval, we call B a k-cube. Th

APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "K-chordal Graphs"

1

Chepoi, Victor D., Feodor F. Dragan, and Chenyu Yan. "Additive Spanners for k-Chordal Graphs." In Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2003. http://dx.doi.org/10.1007/3-540-44849-7_16.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Watrigant, Rémi, Marin Bougeret, and Rodolphe Giroudeau. "Approximating the Sparsest k-Subgraph in Chordal Graphs." In Approximation and Online Algorithms. Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-08001-7_7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Kammer, Frank, and Torsten Tholey. "The k-Disjoint Paths Problem on Chordal Graphs." In Graph-Theoretic Concepts in Computer Science. Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-11409-0_17.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Dourisboure, Yon. "Compact Routing Schemes for Bounded Tree-Length Graphs and for k-Chordal Graphs." In Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/978-3-540-30186-8_26.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Bougeret, Marin, Nicolas Bousquet, Rodolphe Giroudeau, and Rémi Watrigant. "Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs." In SOFSEM 2014: Theory and Practice of Computer Science. Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-04298-5_14.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Kosowski, Adrian, Bi Li, Nicolas Nisse, and Karol Suchan. "k-Chordal Graphs: From Cops and Robber to Compact Routing via Treewidth." In Automata, Languages, and Programming. Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-31585-5_54.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

DeHaan, Ian, and Zachary Friggstad. "Approximate Minimum Sum Colorings and Maximum k-Colorable Subgraphs of Chordal Graphs." In Lecture Notes in Computer Science. Springer Nature Switzerland, 2023. http://dx.doi.org/10.1007/978-3-031-38906-1_22.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Conte, Alessio, Mamadou Moustapha Kanté, Yota Otachi, Takeaki Uno, and Kunihiro Wasa. "Efficient Enumeration of Maximal k-Degenerate Subgraphs in a Chordal Graph." In Lecture Notes in Computer Science. Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-62389-4_13.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Amanathulla, Sk, and Madhumangal Pal. "L(h,k)-Labeling of Intersection Graphs." In Handbook of Research on Advanced Applications of Graph Theory in Modern Society. IGI Global, 2020. http://dx.doi.org/10.4018/978-1-5225-9380-5.ch007.

Full text

Abstract:

One important problem in graph theory is graph coloring or graph labeling. Labeling problem is a well-studied problem due to its wide applications, especially in frequency assignment in (mobile) communication system, coding theory, ray crystallography, radar, circuit design, etc. For two non-negative integers, labeling of a graph is a function from the node set to the set of non-negative integers such that if and if, where it represents the distance between the nodes. Intersection graph is a very important subclass of graph. Unit disc graph, chordal graph, interval graph, circular-arc graph, permutation graph, trapezoid graph, etc. are the important subclasses of intersection graphs. In this chapter, the authors discuss labeling for intersection graphs, specially for interval graphs, circular-arc graphs, permutation graphs, trapezoid graphs, etc., and have presented a lot of results for this problem.

APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "K-chordal Graphs"

1

Araujo, Julio, Alexandre Cezar, Carlos Vinícius Gomes Costa Lima, Vinicius Fernandes Dos Santos, and Ana Shirley Ferreira Silva. "Proper Orientations of Chordal Graphs." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2020. http://dx.doi.org/10.5753/etc.2020.11080.

Full text

Abstract:

An orientation D of a graph G = (V, E) is a digraph obtained from G by replacing each edge by exactly one of the two possible arcs with the same end vertices. For each v ∈ V(G), the indegree of v in D, denoted by dD−(v), is the number of arcs with head v in D. An orientation D of G is proper if dD−(u) ≠ dD−(v), for all uv ∈ E(G). An orientation with maximum indegree at most k is called a k-orientation. The proper orientation number of G, denoted by χ→(G), is the minimum integer k such that G admits a proper k-orientation. We prove that determining whether χ→(G) ≤ k is NP-complete for chordal g

APA, Harvard, Vancouver, ISO, and other styles

2

Sobral, Gabriel A. G., Marina Groshaus, and André L. P. Guedes. "Biclique edge-choosability in some classes of graphs∗." In II Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2017. http://dx.doi.org/10.5753/etc.2017.3203.

Full text

Abstract:

In this paper we study the problem of coloring the edges of a graph for any k-list assignment such that there is no maximal monochromatic biclique, in other words, the k-biclique edge-choosability problem. We prove that the K3free graphs that are not odd cycles are 2-star edge-choosable, chordal bipartite graphs are 2-biclique edge-choosable and we present a lower bound for the biclique choice index of power of cycles and power of paths. We also provide polynomial algorithms to compute a 2-biclique (star) edge-coloring for K3-free and chordal bipartite graphs for any given 2-list assignment to

APA, Harvard, Vancouver, ISO, and other styles

3

Santos, Tanilson D., Jayme Szwarcfiter, Uéverton S. Souza, and Claudson F. Bornstein. "On the Helly Property of Some Intersection Graphs." In Concurso de Teses e Dissertações da SBC. Sociedade Brasileira de Computação, 2021. http://dx.doi.org/10.5753/ctd.2021.15752.

Full text

Abstract:

An EPG graph G is an edge-intersection graph of paths on a grid. In this thesis, we analyze structural characterizations and complexity aspects regarding EPG graphs. Our main focus is on the class of B1-EPG graphs whose intersection model satisfies well-known the Helly property, called Helly-B1-EPG. We show that the problem of recognizing Helly-B1-EPG graphs is NP-complete. Besides, other intersection graph classes such as VPG, EPT, and VPT were also studied. We completely solve the problem of determining the Helly and strong Helly numbers of Bk-EPG graphs and Bk-VPG graphs for each non-negati

APA, Harvard, Vancouver, ISO, and other styles

4

Andrade, Davi de, and Ana Silva. "On the Complexity of Subfall Coloring of Graphs." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2021. http://dx.doi.org/10.5753/etc.2021.16383.

Full text

Abstract:

Given a graph G and a proper k-coloring f of G, a b-vertex in f is a vertex that is adjacent to every color class but its own. If every vertex is a b-vertex, then f is a fall k-coloring; and G has a subfall k-coloring if there is an induced H $\subseteq$ G such that H has a fall k-coloring. The subfall chromatic number of G is the largest positive integer $\psi_{fs}(G)$ such that G has a subfall $\psi_{fs}(G)$-coloring. We prove that deciding if a graph G has a subfall k-coloring is NP-complete for k $\geq$ 4, and characterize graphs having a subfall 3-coloring. This answers a question posed b

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!