Výsledky vyhledávání - "Trapezoid graph"

Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs

Autor: Ba Thai Pham, Viet Dung Nguyen, Phan Thuan Do

Publikováno v: Fundamenta Informaticae. 182:257-283

We first design an $\mathcal{O}(n^2)$ solution for finding a maximum induced matching in permutation graphs given their permutation models, based on a dynamic programming algorithm with the aid of the sweep line technique. With the support of the dis

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::926d9084897feefa9ef510fc85617a22
https://doi.org/10.3233/fi-2021-2073

Zobrazit plný text záznamu

Clique Dominating Sets of Direct Product Graph of Cayley Graphs with Arithmetic Graphs

Autor: M. Manjuri, B. Maheswari

Publikováno v: International Journal of Computer Applications. 174:43-49

Graph Theory is one of the most flourishing branches of modern Mathematics finding widest applications in all most all branches of Science & Technology. It is applied in diverse areas such as social sciences, linguistics, physical sciences, communica

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::c345e02121c87f83e7b7086b85ca2603
https://doi.org/10.5120/ijca2021921114

Zobrazit plný text záznamu

Algorithm for the Vertex Connectivity Problem on Circular Trapezoid Graphs

Autor: Yoko Nakajima, Yuto Tamori, Hirotoshi Honma, Kento Nishimura

Publikováno v: Journal of Applied Mathematics and Physics. :2595-2602

The vertex connectivity k(G) of a graph G is the minimum number of nodes whose deletion disconnects it. Graph connectivity is one of the most fundamental problems in graph theory. In this paper, we designed an O(n2) time algorithm to solve connectivi

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::7d6ed4f9de3237e8d954617281433c8d
https://doi.org/10.4236/jamp.2019.711177

Zobrazit plný text záznamu

L(3,2,1)-Labeling problems on trapezoid graphs

Autor: Sk Amanathulla, Madhumangal Pal

Publikováno v: Discrete Mathematics, Algorithms and Applications. 13

In graph theory, one of the most important problems is graph labeling. Labeling of graph has a very wide range of applications in [Formula: see text]-ray crystallography, missile guidance, coding theory, signal processing, radar, data base management

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::34ed006ba26f09a26d7e8c4daac8de0a
https://doi.org/10.1142/s1793830921500683

Zobrazit plný text záznamu

Algorithms and Complexity of s-Club Cluster Vertex Deletion

Autor: L. Sunil Chandran, Sajith Padinhatteeri, Raji R. Pillai, Dibyayan Chakraborty

Publikováno v: Lecture Notes in Computer Science ISBN: 9783030799861
IWOCA

An s-club is a graph which has diameter at most s. Let G be a graph. A set of vertices $D\subseteq V(G)$ is an s-club deleting (s -CD) set if each connected component of $G-D$ is an s-club. In the s -Club Cluster Vertex Deletion (s -CVD) problem,

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::57b8f668fee9f0e5e2204872fd38c733
https://doi.org/10.1007/978-3-030-79987-8_11

Zobrazit plný text záznamu

Independence-domination duality in weighted graphs

Autor: Ron Aharoni, Irina Gorelik

Publikováno v: Discrete Mathematics. 341:2332-2336

Given a partition V = ( V 1 , … , V m ) of the vertex set of a graph G , an independent transversal (IT) is an independent set in G that contains one vertex from each V i . A fractional IT is a non-negative real valued function on V ( G ) that repr

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3c576b15911877adb1da5bd20b7762cf
https://doi.org/10.1016/j.disc.2018.05.005

Zobrazit plný text záznamu

An Optimal Parallel Algorithm for Constructing a Spanning Tree on Proper Circle Trapezoid Graphs

Autor: Atsushi Sasaki, Shino Nagasaki, Hirotoshi Honma, Yoko Nakajima

Publikováno v: Journal of Applied Mathematics and Physics. :1649-1658

Given a simple graph G with n vertices and m edges, the spanning tree problem is to find a spanning tree for a given graph G. This problem has many applications, such as electric power systems, computer network design and circuit analysis. For a simp

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::3151f45d516fc2c856ea9d31a3048ce7
https://doi.org/10.4236/jamp.2018.68141

Zobrazit plný text záznamu

Gap-planar graphs

Autor: Bae, Sang Won, Baffier, Jean Francois, Chun, Jinhee, Eades, Peter, Eickmeyer, Kord, Grilli, Luca, Hong, Seok Hee, Korman, Matias, Montecchiani, Fabrizio, Rutter, Ignaz, Tóth, Csaba D., Frati, F., Ma, K-L.

Publikováno v: Graph Drawing and Network Visualization-25th International Symposium, GD 2017, Revised Selected Papers, 531-545
STARTPAGE=531;ENDPAGE=545;TITLE=Graph Drawing and Network Visualization-25th International Symposium, GD 2017, Revised Selected Papers
arXiv. Cornell University Library
Lecture Notes in Computer Science ISBN: 9783319739144
Graph Drawing

We introduce the family of $k$-gap-planar graphs for $k \geq 0$, i.e., graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge is assigned at most $k$ of its crossings. This definition is motivated

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::de5502620f8c3423469ea3c5046f7fb0
https://doi.org/10.1007/978-3-319-73915-1_41

Zobrazit plný text záznamu

Akademický článek

Optimal Sequential and Parallel Algorithms for Cut Vertices and Bridges on Trapezoid Graphs

Autor: Hon-Chan Chen

Publikováno v: Discrete Mathematics & Theoretical Computer Science, Vol Vol. 6 no. 2 (2004)

Let G be a graph. A component of G is a maximal connected subgraph in G. A vertex v is a cut vertex of G if k(G-v) > k(G), where k(G) is the number of components in G. Similarly, an edge e is a bridge of G if k(G-e) > k(G). In this paper, we will pro

Externí odkaz: https://doaj.org/article/be28cc81bccc4b5f9fda192e8ba05a5c

Zobrazit plný text záznamu

Vyhledávací nástroje:

Upřesnit hledání