首页 | 本学科首页   官方微博 | 高级检索  
     


On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions
Authors:Marc Hellmuth  Nicolas Wieseke
Affiliation:1.Department of Mathematics and Computer Science,University of Greifswald,Greifswald,Germany;2.Center for Bioinformatics,Saarland University,Saarbrücken,Germany;3.Parallel Computing and Complex Systems Group, Department of Computer Science,Leipzig University,Leipzig,Germany
Abstract:Tree representations of (sets of) symmetric binary relations, or equivalently edge-colored undirected graphs, are of central interest, e.g. in phylogenomics. In this context symbolic ultrametrics play a crucial role. Symbolic ultrametrics define an edge-colored complete graph that allows to represent the topology of this graph as a vertex-colored tree. Here, we are interested in the structure and the complexity of certain combinatorial problems resulting from considerations based on symbolic ultrametrics, and on algorithms to solve them.This includes, the characterization of symbolic ultrametrics that additionally distinguishes between edges and non-edges of arbitrary edge-colored graphs G and thus, yielding a tree representation of G, by means of so-called cographs. Moreover, we address the problem of finding “closest” symbolic ultrametrics and show the NP-completeness of the three problems: symbolic ultrametric editing, completion and deletion. Finally, as not all graphs are cographs, and hence, do not have a tree representation, we ask, furthermore, what is the minimum number of cotrees needed to represent the topology of an arbitrary non-cograph G. This is equivalent to find an optimal cograph edge k-decomposition ({E_1,dots ,E_k}) of E so that each subgraph ((V,E_i)) of G is a cograph. We investigate this problem in full detail, resulting in several new open problems, and NP-hardness results.For all optimization problems proven to be NP-hard we will provide integer linear program formulations to solve them.
Keywords:
本文献已被 SpringerLink 等数据库收录!
相似文献(共20条):
[1]、de Figueiredo,C. M. H.,Patrão,C. S. R.,Sasaki,D.,Valencia-Pabon,M..On total and edge coloring some Kneser graphs[J].Journal of Combinatorial Optimization,2022,44(1):119-135.
[2]、Bumtle Kang,Suh-Ryung Kim,Ji Yeon Park.On consecutive edge magic total labelings of connected bipartite graphs[J].Journal of Combinatorial Optimization,2017,33(1):13-27.
[3]、Jingjing Huo,Yiqiao Wang,Weifan Wang.Neighbor-sum-distinguishing edge choosability of subcubic graphs[J].Journal of Combinatorial Optimization,2017,34(3):742-759.
[4]、Boram Park,Suh-Ryung Kim,Hye Kyung Kim.On the cores of games arising from integer edge covering functions of graphs[J].Journal of Combinatorial Optimization,2013,26(4):786-798.
[5]、Muhammad Kamran Siddiqui,Deeba Afzal,Muhammad Ramzan Faisal.Total edge irregularity strength of accordion graphs[J].Journal of Combinatorial Optimization,2017,34(2):534-544.
[6]、Wei,Meiqin,Yue,Jun,Chen,Lily.The effect of vertex and edge deletion on the edge metric dimension of graphs[J].Journal of Combinatorial Optimization,2022,44(1):331-342.
[7]、Jin-Xin Zhou.Atoms of cyclic edge connectivity in regular graphs[J].Journal of Combinatorial Optimization,2016,31(1):382-395.
[8]、Liu,Zhuoya,Xu,Changqing.Adjacent vertex distinguishing edge coloring of IC-planar graphs[J].Journal of Combinatorial Optimization,2022,43(4):710-726.
[9]、Weifan Wang,Qiaojun Shu,Yiqiao Wang.Acyclic edge coloring of planar graphs without 4-cycles[J].Journal of Combinatorial Optimization,2013,25(4):562-586.
[10]、Aneesh,D. H.,Mohanapriya,A.,Renjith,P.,Sadagopan,N..Steiner tree in k-star caterpillar convex bipartite graphs: a dichotomy[J].Journal of Combinatorial Optimization,2022,44(2):1221-1247.
[11]、Pawan Aurora,Sumit Singh,Shashank K. Mehta.Partial degree bounded edge pacing problem for graphs and $$$$-uniform hypergraphs[J].Journal of Combinatorial Optimization,2016,32(1):159-173.
[12]、Jean Cardinal,Erik D. Demaine,Samuel Fiorini,Gwenaël Joret,Ilan Newman,Oren Weimann.The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs[J].Journal of Combinatorial Optimization,2013,25(1):19-46.
[13]、Huijuan Wang,Bin Liu,Xin Zhang,Lidong Wu,Weili Wu,Hongwei Gao.List edge and list total coloring of planar graphs with maximum degree 8[J].Journal of Combinatorial Optimization,2016,32(1):188-197.
[14]、Hao Chen,Zihan Lei,Tian Liu,Ziyang Tang,Chaoyi Wang,Ke Xu.Complexity of domination,hamiltonicity and treewidth for tree convex bipartite graphs[J].Journal of Combinatorial Optimization,2016,31(1):95-117.
[15]、Muhuo Liu,Baogang Xu.On judicious partitions of graphs[J].Journal of Combinatorial Optimization,2016,31(4):1383-1398.
[16]、Chengchao Yan,Danjun Huang,Dong Chen,Weifan Wang.Adjacent vertex distinguishing edge colorings of planar graphs with girth at least five[J].Journal of Combinatorial Optimization,2014,28(4):893-909.
[17]、Haili Pan,Daqing Yang.On total weight choosability of graphs[J].Journal of Combinatorial Optimization,2013,25(4):766-783.
[18]、Michael Hallaway,Cong X. Kang,Eunjeong Yi.On metric dimension of permutation graphs[J].Journal of Combinatorial Optimization,2014,28(4):814-826.
[19]、Mekkia Kouider,Mohamed Zamime.On the b-coloring of tight graphs[J].Journal of Combinatorial Optimization,2017,33(1):202-214.
[20]、Xin Zhang,Jianfeng Hou,Guizhen Liu.On total colorings of 1-planar graphs[J].Journal of Combinatorial Optimization,2015,30(1):160-173.
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号