Results 241 to 250 of about 123,539 (262)
Some of the next articles are maybe not open access.
Approximation algorithms for graph augmentation
Journal of Algorithms, 1992Summary: The problem of increasing both edge and vertex connectivity of a graph at an optimal cost is studied. Since the general problem is NP-hard, we focus on efficient approximation schemes that come within a constant factor from the optimal. Previous algorithms either do not take edge costs into consideration, or they run slower than our algorithm.
Khuller, Samir, Thurimella, Ramakrishna
openaire +2 more sources
Regular Augmentation of Planar Graphs
Algorithmica, 2014This paper studies the problem of augmenting a planar graph such that it becomes \(k\)-regular, \(c\)-connected and remains planar, either in the sense that the augmented graph is planar, or in the sense that the input graph has a fixed (topological) planar embedding that can be extended to a planar embedding of the augmented graph.
Hartmann, Tanja +2 more
openaire +3 more sources
Journal of Algorithms, 1996
Summary: We show that for outerplanar graphs \(G\) the problem of augmenting \(G\) by adding a minimum number of edges such that the augmented graph \(G'\) is planar and bridge-connected, biconnected, or triconnected can be solved in linear time and space.
openaire +3 more sources
Summary: We show that for outerplanar graphs \(G\) the problem of augmenting \(G\) by adding a minimum number of edges such that the augmented graph \(G'\) is planar and bridge-connected, biconnected, or triconnected can be solved in linear time and space.
openaire +3 more sources
Optimal Mixed Graph Augmentation
SIAM Journal on Computing, 1987We consider an augmentation problem on mixed graphs that generalizes and unifies two augmentation problems considered by \textit{K. P. Eswaran} and \textit{R. E. Tarjan} [ibid. 5, 653-665 (1976; Zbl 0346.05112)]. The mixed augmentation problem has applications in the design of communication networks, and forms of mixed augmentation problem are central ...
openaire +1 more source
Globally Rigid Augmentation of Rigid Graphs
SIAM Journal on Discrete Mathematics, 2022zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Csaba Király, András Mihálykó
openaire +2 more sources
Augmenting the Connectivity of Outerplanar Graphs
Algorithmica, 2008zbMATH Open Web Interface contents unavailable due to conflicting licenses.
García, A. +3 more
openaire +2 more sources
Smallest Augmentations to Biconnect a Graph
SIAM Journal on Computing, 1977We provide an $O(| V | + | E |)$ algorithm which, given a graph G, finds a smallest set of edges which, when added to G, produces a graph with no cutpoints.
Rosenthal, Arnie, Goldner, Anita
openaire +2 more sources
Effective and efficient graph augmentation in large graphs
2016 IEEE International Conference on Big Data (Big Data), 2016The graph augmentation problem seeks to suggest new edges that, when added to an input graph, improve the overall connectivity of the nodes. For social network applications, the latter is typically computed as the average shortest path length in the network.
Ioanna Filippidou, Yannis Kotidis
openaire +1 more source
Proper Augmented Marked Graphs
2014A special type of augmented marked graphs, proper augmented marked graphs, not only inherit the properties of augmented marked graphs but also possess some special properties. This chapter provides a comprehensive description of proper augmented marked graphs. It starts with the definition of proper augmented marked graphs.
openaire +1 more source
Multi-relational graph contrastive learning with learnable graph augmentation
Neural NetworksMulti-relational graph learning aims to embed entities and relations in knowledge graphs into low-dimensional representations, which has been successfully applied to various multi-relationship prediction tasks, such as information retrieval, question answering, and etc. Recently, contrastive learning has shown remarkable performance in multi-relational
Xian Mo +5 more
openaire +2 more sources