Zobrazeno 1 - 10
of 485
pro vyhledávání: '"Trivially perfect graph"'
Publikováno v:
Lecture Notes in Computer Science, 13201
Algorithms for Big Data
Lecture Notes in Computer Science ISBN: 9783031215339
Algorithms for Big Data
Lecture Notes in Computer Science ISBN: 9783031215339
We consider the problem of transforming a given graph into a quasi-threshold graph using a minimum number of edge additions and deletions. Building on the previously proposed heuristic Quasi-Threshold Mover (QTM), we present improvements both in term
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c511dc7bc371358d712b21ae361b39b3
https://hdl.handle.net/20.500.11850/594017
https://hdl.handle.net/20.500.11850/594017
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Publikováno v:
eTIME-2019 – INTERNATIONAL CONFERENCE ON EMERGING TRENDS IN MECHANICAL ENGINEERING.
Gallai graph of a graph G is a graph whose vertices are the edges of G and the adjacency of the vertices depends on whether they are part of a triangle or not in G. We find some forbidden subgraph characterization of graphs for which Gallai graph is
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ae57c17508a468164c4427924035151e
https://doi.org/10.1063/5.0006807
https://doi.org/10.1063/5.0006807
Autor:
Michał Pilipczuk, Pål Grønås Drange
Publikováno v:
Algorithmica. 80:3481-3524
We give a kernel with $O(k^7)$ vertices for Trivially Perfect Editing, the problem of adding or removing at most $k$ edges in order to make a given graph trivially perfect. This answers in affirmative an open question posed by Nastos and Gao, and by
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c37b848923b64e234fdb7a86e58abbaa
https://doi.org/10.1007/s00453-017-0401-6
https://doi.org/10.1007/s00453-017-0401-6
Autor:
F. A. Sharifov
Publikováno v:
Cybernetics and Systems Analysis. 53:753-758
It is shown that any graph has a perfect matching if and only if a specially defined vector is the base of extended polymatroid associated with submodular function defined on subsets of vertex set. Based on this fact, different algorithms for testing
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::af53374cb870a136203f9c6702b76549
https://doi.org/10.1007/s10559-017-9977-8
https://doi.org/10.1007/s10559-017-9977-8
Autor:
G. V Ghodasara, S. G Sonchhatra
Publikováno v:
International Journal of Mathematics Trends and Technology. 46:62-65
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::2fe3786851d5eed53013e97b5c8d179c
https://doi.org/10.14445/22315373/ijmtt-v46p512
https://doi.org/10.14445/22315373/ijmtt-v46p512
Autor:
Fuji Zhang, Yuqing Lin
Publikováno v:
Theoretical Computer Science. 675:82-88
In this paper, we present a linear algorithm to find a perfect matching in a polyomino graph or show that there are none.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f826e194a4f8e3f77441e50bc437c070
https://doi.org/10.1016/j.tcs.2017.02.028
https://doi.org/10.1016/j.tcs.2017.02.028
Publikováno v:
ACM Transactions on Computation Theory. 9:1-20
A red-blue graph is a graph where every edge is colored either red or blue. The exact perfect matching problem asks for a perfect matching in a red-blue graph that has exactly a given number of red edges. We show that for complete and bipartite compl
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e42cfdfa75f61957023cf34190857724
https://doi.org/10.1145/3041402
https://doi.org/10.1145/3041402
Publikováno v:
Discrete Mathematics. 340:740-745
In this article, we characterize various algebraic and order structures whose zero-divisor graphs are perfect graphs. We strengthen the result of Chenź(2003, Theorem 2.5) by providing a simpler proof of Beck's conjecture for the class of finite redu
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::39093a349c5e36eb86c34ac8e7d6c5d9
https://doi.org/10.1016/j.disc.2016.11.027
https://doi.org/10.1016/j.disc.2016.11.027
Autor:
Yue-Li Wang, Ton Kloks
Publikováno v:
Optimization Letters. 12:535-549
A retract of a graph G is an induced subgraph H of G such that there exists a homomorphism $$\rho :G \rightarrow H$$ . When both G and H are cographs, we show that the problem to determine whether H is a retract of G is NP-complete; moreover, we show
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::20925abbc1c01a6276fff00110c15369
https://doi.org/10.1007/s11590-017-1126-9
https://doi.org/10.1007/s11590-017-1126-9