Press "Enter" to skip to content

Algorithms and Models for the Web Graph: 12th International by David F. Gleich, Júlia Komjáthy, Nelly Litvak

By David F. Gleich, Júlia Komjáthy, Nelly Litvak

This publication constitutes the complaints of the twelfth overseas Workshop on Algorithms and versions for the internet Graph, WAW 2015, held in Eindhoven, The Netherlands, in December 2015.

The 15 complete papers provided during this quantity have been conscientiously reviewed and chosen from 24 submissions. they're prepared in topical sections named: houses of enormous graph versions, dynamic techniques on huge graphs, and homes of PageRank on huge graphs.

Show description

Read Online or Download Algorithms and Models for the Web Graph: 12th International Workshop, WAW 2015, Eindhoven, The Netherlands, December 10-11, 2015, Proceedings PDF

Similar algorithms books

The Nature of Code

How will we seize the unpredictable evolutionary and emergent houses of nature in software program? How can realizing the mathematical rules in the back of our actual international support us to create electronic worlds? This booklet makes a speciality of quite a number programming suggestions and strategies in the back of desktop simulations of usual structures, from effortless thoughts in arithmetic and physics to extra complicated algorithms that permit refined visible effects.

Creating New Medical Ontologies for Image Annotation: A Case Study

Growing New clinical Ontologies for photograph Annotation specializes in the matter of the clinical photos computerized annotation approach, that's solved in an unique demeanour by way of the authors. all of the steps of this procedure are defined intimately with algorithms, experiments and effects. the unique algorithms proposed via authors are in comparison with different effective related algorithms.

Algorithms and Models for the Web-Graph: 7th International Workshop, WAW 2010, Stanford, CA, USA, December 13-14, 2010. Proceedings

This ebook constitutes the refereed court cases of the seventh overseas Workshop on Algorithms and types for the Web-Graph, WAW 2010, held in Stanford, CA, united states, in December 2010, which was once co-located with the sixth overseas Workshop on web and community Economics (WINE 2010). The thirteen revised complete papers and the invited paper awarded have been rigorously reviewed and chosen from 19 submissions.

Additional info for Algorithms and Models for the Web Graph: 12th International Workshop, WAW 2015, Eindhoven, The Netherlands, December 10-11, 2015, Proceedings

Example text

It captures how “tree-like” a graph is in terms of its metric structure, and has received attention in the analysis of networks and informatics graphs. We refer the reader to [6,15,17,18], and references therein, for details on the motivating network applications. There are several ways of characterizing δ-hyperbolic metric spaces, all of which are equivalent up to constant factors [5,7,13]. Since graphs are naturally geodesic metric spaces when distance is defined using shortest paths, we will use the definition based on δ-slim triangles (originally attributed to Rips [5,13]).

Algorithmically, this property is 1 Not related to the notion of expander graphs. F. Gleich et al. ): WAW 2015, LNCS 9479, pp. 29–41, 2015. 1007/978-3-319-26784-5 3 30 M. Farrell et al. extremely useful: every first-order-definable problem is decidable in linear fpttime in these classes [10]. For example, counting the number of appearances of a fixed pattern graph as a subgraph can be computed in linear time [9,22]. We also consider δ-hyperbolicity, which restricts the structure of shortest-path distances in the graph to be tree-like.

Definition 4 (Bounded expansion). A graph class G has bounded expansion if there exists a function f such that for all r, we have ∇r (G) < f (r). Hyperbolicity, Degeneracy, and Expansion of Random Intersection Graphs 33 When introduced, bounded expansion was originally defined using an equivalent characterization based on the notion of shallow minors (cf. [19]): H is a r-shallow minor of G if H can be obtained from G by contracting disjoint subgraphs of radius at most r. In the context of our paper, however, the topological shallow minor variant proves more useful, and we restrict our attention to this setting.

Download PDF sample

Rated 4.81 of 5 – based on 14 votes