Buscar
Mostrando ítems 51-60 de 403
Using Compressed Suffix-Arrays for a Compact Representation of Temporal-Graphs
(2018)
Temporal graphs represent binary relationships that change along time. They can model the dynamism of, for example, social and communication networks. Temporal graphs are defined as sets of contacts that are edges tagged ...
Recent results on containment graphs of paths in a tree
(Elsevier Science, 2018-08)
In this paper, motivated by the questions posed by Spinrad in Spinrad (2003) and Golumbic and Trenk (2004), we investigate those posets that admit a containment model mapping vertices into paths of a tree and their ...
Characterization and linear-time detection of minimal obstructions to concave-round graphs and the circular-ones property
(John Wiley & Sons Inc, 2020-02-20)
A graph is concave-round if its vertices can be circularly enumerated so that the closed neighborhood of each vertex is an interval in the enumeration. In this study, we give a minimal forbidden induced subgraph characterization ...
Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter II: algorithms
(Brown University. Department of Computer Science, 2017-04)
This is the second and last chapter of a work in which we consider the unrestricted, minimal, and bounded representation problems for unit interval (UIG) and unit circular-arc (UCA) graphs. In the unrestricted version ...
On dominating set polyhedra of circular interval graphs
(Elsevier Science, 2021-04)
Clique-node and closed neighborhood matrices of circular interval graphs are circular matrices. The stable set polytope and the dominating set polytope on these graphs are therefore closely related to the set packing ...
Thinness of product graphs
(Elsevier Science, 2022)
Sources and sinks in comparability graphs
(Kluwer Academic PublDordrechtHolanda, 1997)
NP-completeness results for edge modification problems
(ELSEVIER, 2006-08-15)
The aim of edge modification problems is to change the edge set of a given graph as little as possible in order to satisfy a certain property. Edge modification problems in graphs have a lot of applications in different ...
Coloração de arestas em grafos split-comparabilidade e split-intervalos
(Universidade Tecnológica Federal do ParanáPonta GrossaBrasilPrograma de Pós-Graduação em Ciência da ComputaçãoUTFPR, 2021-04-20)
A proper edge coloring of a graph is an assignment of colors to its edges such that edges incident with the same vertex have distinct colors. The Edge Coloring Problem is answering, given a graph, which is the least number ...
Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter I: theory
(Brown University, 2017-04)
This is the first of two chapters of a work in which we consider the unrestricted, minimal, and bounded representation problems for unit interval (UIG) and unit circular-arc (UCA) graphs. In the unrestricted version, a ...