𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The maximum edit distance from hereditary graph properties

✍ Scribed by Noga Alon; Uri Stav

Book ID
108167440
Publisher
Elsevier Science
Year
2008
Tongue
English
Weight
285 KB
Volume
98
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the editing distance of graphs
On the editing distance of graphs
✍ Maria Axenovich; AndrΓ© KΓ©zdy; Ryan Martin πŸ“‚ Article πŸ“… 2008 πŸ› John Wiley and Sons 🌐 English βš– 169 KB πŸ‘ 2 views

## Abstract An edge‐operation on a graph __G__ is defined to be either the deletion of an existing edge or the addition of a nonexisting edge. Given a family of graphs $\cal G$, the editing distance from __G__ to $\cal G$ is the smallest number of edge‐operations needed to modify __G__ into a graph

The Speed of Hereditary Properties of Gr
The Speed of Hereditary Properties of Graphs
✍ JΓ³zsef Balogh; BΓ©la BollobΓ‘s; David Weinreich πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 217 KB

Given a property P of graphs, write P n for the set of graphs with vertex set [n] having property P. The growth or speed of a property P can be discussed in terms of the values of |P n |. For properties with |P n | <n n hereditary properties are surprisingly well determined by their speeds. Sharpeni