Edge Elimination and Weighted Graph Classes

Autor:	Matjaž Krnc, Nina Chiarelli, Nevena Pivač, Jesse Beisegel, Martin Strehler, Robert Scheffler, Ekkehard Köhler, Martin Milanič
Rok vydání:	2020
Předmět:	Combinatorics Monotonic function Recognition algorithm Similarity theory Graph MathematicsofComputing_DISCRETEMATHEMATICS Mathematics
Zdroj:	Graph-Theoretic Concepts in Computer Science ISBN: 9783030604394 WG
Popis:	Edge-weighted graphs play an important role in the theory of Robinsonian matrices and similarity theory, particularly via the concept of level graphs, that is, graphs obtained from an edge-weighted graph by removing all sufficiently light edges. This naturally leads to a generalization of the concept of a graph class to the weighted case by requiring that all level graphs belong to the class. We examine some types of monotonicity of graph classes, such as sandwich monotonicity, to construct edge elimination schemes of edge-weighted graphs. This leads to linear-time recognition algorithms of weighted graphs for which all level graphs are split, threshold, or chain graphs.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::add47f59de2845c915980e01d66d5462 https://doi.org/10.1007/978-3-030-60440-0_11 Zobrazit plný text záznamu