1,721,001 research outputs found
On the geodetic iteration number of the contour of a graph
No full textLet G be a graph and S be a subset of vertices of G. With I[S] we denote the set of all vertices on some geodesic (shortest path) between two vertices of S. A contour vertex of a graph is one whose eccentricity is at least as big as all its neighbors' eccentricities. Let C be the set of contour vertices of a graph. We provide the first example of a graph where I[I[C]] do not coincide with the vertex set of the graph
On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs
No full textIn this paper we show that the problem of finding a chordless path between a vertex s and a vertex t containing a vertex v remains NP-complete in bipartite graphs, thereby strengthening the previous results on the same problem. We show a relation between this problem and two interval operators: the simple path interval operator in hypergraphs and the even-chorded path interval operator in graphs. We show that the problem of computing the two mentioned intervals is NP-complete
Fully dynamic algorithm for chordal graphs with O(1) query-time and O(n2) update-time
No full textWe propose dynamic algorithms and data structures for chordal graphs supporting the following operation: determine if an edge can be added or removed from the graph while preserving the chordality in O(1) time. We show that the complexity of the algorithms for updating the data structures when an edge is actually inserted or deleted is O(n2) where n is the number of vertices of the graph
Fast minimal triangulation algorithm using minimum degree criterion
No full textWe propose an algorithm for minimal triangulation which, using simple and efficient strategy, subdivides the input graph in different, almost non-overlapping, subgraphs. Using the technique of matrix multiplication for saturating the minimal separators, we show that the partition of the graph can be computed in time O(nα) where nα is the time required by the binary matrix multiplication. After saturating the minimal separators, the same procedure is recursively applied on each subgraphs. We also present a variant of the algorithm in which the minimum degree criterion is used. In this way, we obtain an algorithm that uses minimum degree criterion and at the same time produces a minimal triangulation, thus shedding new light on the effectiveness of the minimum degree heuristics
Empirical study on label smoothing in neural networks
No full textNeural networks are now day routinely employed in the classification of sets of objects, which consists in predicting
the class label of an object. The softmax function is a popular choice of the output function in neural networks.
It is a probability distribution of the class labels and the label with maximum probability represents the prediction
of the neural network, given the object being classified. The softmax function is also used to compute the loss
function, which evaluates the error made by the network in the classification task. In this paper we consider a
simple modification to the loss function, called label smoothing. We experimented this modification by training a
neural network using 12 data sets, all containing a total of about 1x10^6 images. We show that this modification
allow a neural network to achieve a better accuracy in the classification task
- …
