Tight Bounds for Coalescing-Branching Random Walks on Regular Graphs Article Swipe

PDF

Petra Berenbrin , George Giakkoupis , Peter Kling ·

YOU? · · 2018 · Open Access · · DOI: https://doi.org/10.1137/1.9781611975031.112

International audience

Related Topics

Mathematical Analysis

Public Relations

Mechanical Engineering

Engineering

Concepts

Random walk Combinatorics Mathematics Upper and lower bounds Discrete mathematics Branching process Expander graph Graph Cover (algebra) Rumor Statistics Mathematical analysis Public relations Mechanical engineering Political science Engineering

Metadata

Type: book-chapter
Language: en
Landing Page: https://doi.org/10.1137/1.9781611975031.112
PDF: https://epubs.siam.org/doi/pdf/10.1137/1.9781611975031.112
OA Status: bronze
Cited By: 7
References: 26
Related Works: 10
OpenAlex ID: https://openalex.org/W2780822466

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W2780822466

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.1137/1.9781611975031.112

Digital Object Identifier
Title: Tight Bounds for Coalescing-Branching Random Walks on Regular Graphs

Work title
Type: book-chapter

OpenAlex work type
Language: en

Primary language
Publication year: 2018

Year of publication
Publication date: 2018-01-01

Full publication date if available
Authors: Petra Berenbrin, George Giakkoupis, Peter Kling

List of authors in order
Landing page: https://doi.org/10.1137/1.9781611975031.112

Publisher landing page
PDF URL: https://epubs.siam.org/doi/pdf/10.1137/1.9781611975031.112

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: bronze

Open access status per OpenAlex
OA URL: https://epubs.siam.org/doi/pdf/10.1137/1.9781611975031.112

Direct OA link when available
Concepts: Random walk, Combinatorics, Mathematics, Upper and lower bounds, Discrete mathematics, Branching process, Expander graph, Graph, Cover (algebra), Rumor, Statistics, Mathematical analysis, Public relations, Mechanical engineering, Political science, Engineering

Top concepts (fields/topics) attached by OpenAlex
Cited by: 7

Total citation count in OpenAlex
Citations by year (recent): 2021: 1, 2020: 1, 2019: 5

Per-year citation counts (last 5 years)
References (count): 26

Number of works referenced by this work
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W2780822466
doi	https://doi.org/10.1137/1.9781611975031.112
ids.doi	https://doi.org/10.1137/1.9781611975031.112
ids.mag	2780822466
ids.openalex	https://openalex.org/W2780822466
fwci	4.66868905
type	book-chapter
title	Tight Bounds for Coalescing-Branching Random Walks on Regular Graphs
biblio.issue
biblio.volume
biblio.last_page	1733
biblio.first_page	1715
topics[0].id	https://openalex.org/T10064
topics[0].field.id	https://openalex.org/fields/31
topics[0].field.display_name	Physics and Astronomy
topics[0].score	0.9940000176429749
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/3109
topics[0].subfield.display_name	Statistical and Nonlinear Physics
topics[0].display_name	Complex Network Analysis Techniques
topics[1].id	https://openalex.org/T11152
topics[1].field.id	https://openalex.org/fields/26
topics[1].field.display_name	Mathematics
topics[1].score	0.992900013923645
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/2610
topics[1].subfield.display_name	Mathematical Physics
topics[1].display_name	Stochastic processes and statistical mechanics
topics[2].id	https://openalex.org/T11478
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9853000044822693
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1705
topics[2].subfield.display_name	Computer Networks and Communications
topics[2].display_name	Caching and Content Delivery
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C121194460
concepts[0].level	2
concepts[0].score	0.7185924649238586
concepts[0].wikidata	https://www.wikidata.org/wiki/Q856741
concepts[0].display_name	Random walk
concepts[1].id	https://openalex.org/C114614502
concepts[1].level	1
concepts[1].score	0.6427133083343506
concepts[1].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[1].display_name	Combinatorics
concepts[2].id	https://openalex.org/C33923547
concepts[2].level	0
concepts[2].score	0.5561373233795166
concepts[2].wikidata	https://www.wikidata.org/wiki/Q395
concepts[2].display_name	Mathematics
concepts[3].id	https://openalex.org/C77553402
concepts[3].level	2
concepts[3].score	0.5345211625099182
concepts[3].wikidata	https://www.wikidata.org/wiki/Q13222579
concepts[3].display_name	Upper and lower bounds
concepts[4].id	https://openalex.org/C118615104
concepts[4].level	1
concepts[4].score	0.5337532162666321
concepts[4].wikidata	https://www.wikidata.org/wiki/Q121416
concepts[4].display_name	Discrete mathematics
concepts[5].id	https://openalex.org/C177255742
concepts[5].level	2
concepts[5].score	0.4985215663909912
concepts[5].wikidata	https://www.wikidata.org/wiki/Q4109953
concepts[5].display_name	Branching process
concepts[6].id	https://openalex.org/C154547637
concepts[6].level	3
concepts[6].score	0.48318591713905334
concepts[6].wikidata	https://www.wikidata.org/wiki/Q776602
concepts[6].display_name	Expander graph
concepts[7].id	https://openalex.org/C132525143
concepts[7].level	2
concepts[7].score	0.47298797965049744
concepts[7].wikidata	https://www.wikidata.org/wiki/Q141488
concepts[7].display_name	Graph
concepts[8].id	https://openalex.org/C2780428219
concepts[8].level	2
concepts[8].score	0.44421911239624023
concepts[8].wikidata	https://www.wikidata.org/wiki/Q16952335
concepts[8].display_name	Cover (algebra)
concepts[9].id	https://openalex.org/C2780469804
concepts[9].level	2
concepts[9].score	0.4376674294471741
concepts[9].wikidata	https://www.wikidata.org/wiki/Q878352
concepts[9].display_name	Rumor
concepts[10].id	https://openalex.org/C105795698
concepts[10].level	1
concepts[10].score	0.08983781933784485
concepts[10].wikidata	https://www.wikidata.org/wiki/Q12483
concepts[10].display_name	Statistics
concepts[11].id	https://openalex.org/C134306372
concepts[11].level	1
concepts[11].score	0.0
concepts[11].wikidata	https://www.wikidata.org/wiki/Q7754
concepts[11].display_name	Mathematical analysis
concepts[12].id	https://openalex.org/C39549134
concepts[12].level	1
concepts[12].score	0.0
concepts[12].wikidata	https://www.wikidata.org/wiki/Q133080
concepts[12].display_name	Public relations
concepts[13].id	https://openalex.org/C78519656
concepts[13].level	1
concepts[13].score	0.0
concepts[13].wikidata	https://www.wikidata.org/wiki/Q101333
concepts[13].display_name	Mechanical engineering
concepts[14].id	https://openalex.org/C17744445
concepts[14].level	0
concepts[14].score	0.0
concepts[14].wikidata	https://www.wikidata.org/wiki/Q36442
concepts[14].display_name	Political science
concepts[15].id	https://openalex.org/C127413603
concepts[15].level	0
concepts[15].score	0.0
concepts[15].wikidata	https://www.wikidata.org/wiki/Q11023
concepts[15].display_name	Engineering
keywords[0].id	https://openalex.org/keywords/random-walk
keywords[0].score	0.7185924649238586
keywords[0].display_name	Random walk
keywords[1].id	https://openalex.org/keywords/combinatorics
keywords[1].score	0.6427133083343506
keywords[1].display_name	Combinatorics
keywords[2].id	https://openalex.org/keywords/mathematics
keywords[2].score	0.5561373233795166
keywords[2].display_name	Mathematics
keywords[3].id	https://openalex.org/keywords/upper-and-lower-bounds
keywords[3].score	0.5345211625099182
keywords[3].display_name	Upper and lower bounds
keywords[4].id	https://openalex.org/keywords/discrete-mathematics
keywords[4].score	0.5337532162666321
keywords[4].display_name	Discrete mathematics
keywords[5].id	https://openalex.org/keywords/branching-process
keywords[5].score	0.4985215663909912
keywords[5].display_name	Branching process
keywords[6].id	https://openalex.org/keywords/expander-graph
keywords[6].score	0.48318591713905334
keywords[6].display_name	Expander graph
keywords[7].id	https://openalex.org/keywords/graph
keywords[7].score	0.47298797965049744
keywords[7].display_name	Graph
keywords[8].id	https://openalex.org/keywords/cover
keywords[8].score	0.44421911239624023
keywords[8].display_name	Cover (algebra)
keywords[9].id	https://openalex.org/keywords/rumor
keywords[9].score	0.4376674294471741
keywords[9].display_name	Rumor
keywords[10].id	https://openalex.org/keywords/statistics
keywords[10].score	0.08983781933784485
keywords[10].display_name	Statistics
language	en
locations[0].id	doi:10.1137/1.9781611975031.112
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306463922
locations[0].source.issn
locations[0].source.type	ebook platform
locations[0].source.is_oa	False
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	Society for Industrial and Applied Mathematics eBooks
locations[0].source.host_organization	https://openalex.org/P4310320508
locations[0].source.host_organization_name	Society for Industrial and Applied Mathematics
locations[0].source.host_organization_lineage	https://openalex.org/P4310320508
locations[0].source.host_organization_lineage_names	Society for Industrial and Applied Mathematics
locations[0].license
locations[0].pdf_url	https://epubs.siam.org/doi/pdf/10.1137/1.9781611975031.112
locations[0].version	publishedVersion
locations[0].raw_type	book-chapter
locations[0].license_id
locations[0].is_accepted	True
locations[0].is_published	True
locations[0].raw_source_name	Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms
locations[0].landing_page_url	https://doi.org/10.1137/1.9781611975031.112
locations[1].id	pmh:oai:HAL:hal-01635757v1
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306402512
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	False
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	HAL (Le Centre pour la Communication Scientifique Directe)
locations[1].source.host_organization	https://openalex.org/I1294671590
locations[1].source.host_organization_name	Centre National de la Recherche Scientifique
locations[1].source.host_organization_lineage	https://openalex.org/I1294671590
locations[1].license	other-oa
locations[1].pdf_url
locations[1].version	submittedVersion
locations[1].raw_type	Conference papers
locations[1].license_id	https://openalex.org/licenses/other-oa
locations[1].is_accepted	False
locations[1].is_published	False
locations[1].raw_source_name	SODA 2018 - Proceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms, Jan 2018, New Orleans, United States. pp.1715-1733, ⟨10.1137/1.9781611975031.112⟩
locations[1].landing_page_url	https://inria.hal.science/hal-01635757
indexed_in	crossref
authorships[0].author.id	https://openalex.org/A5107283728
authorships[0].author.orcid
authorships[0].author.display_name	Petra Berenbrin
authorships[0].countries	CA, DE
authorships[0].affiliations[0].institution_ids	https://openalex.org/I18014758
authorships[0].affiliations[0].raw_affiliation_string	Simon Fraser University
authorships[0].affiliations[1].institution_ids	https://openalex.org/I159176309
authorships[0].affiliations[1].raw_affiliation_string	University of Hamburg
authorships[0].institutions[0].id	https://openalex.org/I18014758
authorships[0].institutions[0].ror	https://ror.org/0213rcc28
authorships[0].institutions[0].type	education
authorships[0].institutions[0].lineage	https://openalex.org/I18014758
authorships[0].institutions[0].country_code	CA
authorships[0].institutions[0].display_name	Simon Fraser University
authorships[0].institutions[1].id	https://openalex.org/I159176309
authorships[0].institutions[1].ror	https://ror.org/00g30e956
authorships[0].institutions[1].type	education
authorships[0].institutions[1].lineage	https://openalex.org/I159176309
authorships[0].institutions[1].country_code	DE
authorships[0].institutions[1].display_name	Universität Hamburg
authorships[0].author_position	first
authorships[0].raw_author_name	Petra Berenbrin
authorships[0].is_corresponding	False
authorships[0].raw_affiliation_strings	Simon Fraser University, University of Hamburg
authorships[1].author.id	https://openalex.org/A5006944198
authorships[1].author.orcid	https://orcid.org/0000-0002-8023-4485
authorships[1].author.display_name	George Giakkoupis
authorships[1].affiliations[0].raw_affiliation_string	the World Is Distributed Exploring the tension between scale and coordination
authorships[1].author_position	middle
authorships[1].raw_author_name	George Giakkoupis
authorships[1].is_corresponding	False
authorships[1].raw_affiliation_strings	the World Is Distributed Exploring the tension between scale and coordination
authorships[2].author.id	https://openalex.org/A5007675663
authorships[2].author.orcid	https://orcid.org/0000-0003-0000-8689
authorships[2].author.display_name	Peter Kling
authorships[2].countries	DE
authorships[2].affiliations[0].institution_ids	https://openalex.org/I159176309
authorships[2].affiliations[0].raw_affiliation_string	University of Hamburg
authorships[2].institutions[0].id	https://openalex.org/I159176309
authorships[2].institutions[0].ror	https://ror.org/00g30e956
authorships[2].institutions[0].type	education
authorships[2].institutions[0].lineage	https://openalex.org/I159176309
authorships[2].institutions[0].country_code	DE
authorships[2].institutions[0].display_name	Universität Hamburg
authorships[2].author_position	last
authorships[2].raw_author_name	Peter Kling
authorships[2].is_corresponding	False
authorships[2].raw_affiliation_strings	University of Hamburg
has_content.pdf	True
has_content.grobid_xml	True
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://epubs.siam.org/doi/pdf/10.1137/1.9781611975031.112
open_access.oa_status	bronze
open_access.any_repository_has_fulltext	False
created_date	2018-01-05T00:00:00
display_name	Tight Bounds for Coalescing-Branching Random Walks on Regular Graphs
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T03:46:38.306776
primary_topic.id	https://openalex.org/T10064
primary_topic.field.id	https://openalex.org/fields/31
primary_topic.field.display_name	Physics and Astronomy
primary_topic.score	0.9940000176429749
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/3109
primary_topic.subfield.display_name	Statistical and Nonlinear Physics
primary_topic.display_name	Complex Network Analysis Techniques
related_works	https://openalex.org/W2372853429, https://openalex.org/W2793319716, https://openalex.org/W3110636174, https://openalex.org/W4210503589, https://openalex.org/W2810386322, https://openalex.org/W2908713064, https://openalex.org/W2801267666, https://openalex.org/W4213140416, https://openalex.org/W1975564741, https://openalex.org/W2336106727
cited_by_count	7
counts_by_year[0].year	2021
counts_by_year[0].cited_by_count	1
counts_by_year[1].year	2020
counts_by_year[1].cited_by_count	1
counts_by_year[2].year	2019
counts_by_year[2].cited_by_count	5
locations_count	2
best_oa_location.id	doi:10.1137/1.9781611975031.112
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306463922
best_oa_location.source.issn
best_oa_location.source.type	ebook platform
best_oa_location.source.is_oa	False
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	Society for Industrial and Applied Mathematics eBooks
best_oa_location.source.host_organization	https://openalex.org/P4310320508
best_oa_location.source.host_organization_name	Society for Industrial and Applied Mathematics
best_oa_location.source.host_organization_lineage	https://openalex.org/P4310320508
best_oa_location.source.host_organization_lineage_names	Society for Industrial and Applied Mathematics
best_oa_location.license
best_oa_location.pdf_url	https://epubs.siam.org/doi/pdf/10.1137/1.9781611975031.112
best_oa_location.version	publishedVersion
best_oa_location.raw_type	book-chapter
best_oa_location.license_id
best_oa_location.is_accepted	True
best_oa_location.is_published	True
best_oa_location.raw_source_name	Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms
best_oa_location.landing_page_url	https://doi.org/10.1137/1.9781611975031.112
primary_location.id	doi:10.1137/1.9781611975031.112
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306463922
primary_location.source.issn
primary_location.source.type	ebook platform
primary_location.source.is_oa	False
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	Society for Industrial and Applied Mathematics eBooks
primary_location.source.host_organization	https://openalex.org/P4310320508
primary_location.source.host_organization_name	Society for Industrial and Applied Mathematics
primary_location.source.host_organization_lineage	https://openalex.org/P4310320508
primary_location.source.host_organization_lineage_names	Society for Industrial and Applied Mathematics
primary_location.license
primary_location.pdf_url	https://epubs.siam.org/doi/pdf/10.1137/1.9781611975031.112
primary_location.version	publishedVersion
primary_location.raw_type	book-chapter
primary_location.license_id
primary_location.is_accepted	True
primary_location.is_published	True
primary_location.raw_source_name	Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms
primary_location.landing_page_url	https://doi.org/10.1137/1.9781611975031.112
publication_date	2018-01-01
publication_year	2018
referenced_works	https://openalex.org/W2009356484, https://openalex.org/W1536693177, https://openalex.org/W1885929229, https://openalex.org/W2112749339, https://openalex.org/W2103160469, https://openalex.org/W2084768526, https://openalex.org/W1975564741, https://openalex.org/W2155704505, https://openalex.org/W1564693713, https://openalex.org/W4246933290, https://openalex.org/W2963680590, https://openalex.org/W4230376356, https://openalex.org/W2036027002, https://openalex.org/W2160504298, https://openalex.org/W2949091638, https://openalex.org/W2170807097, https://openalex.org/W2281441226, https://openalex.org/W2039765418, https://openalex.org/W2091712762, https://openalex.org/W2067883080, https://openalex.org/W2311405147, https://openalex.org/W4231916799, https://openalex.org/W2047784567, https://openalex.org/W2737814453, https://openalex.org/W2805389667, https://openalex.org/W2127671443
referenced_works_count	26
abstract_inverted_index.audience	1
abstract_inverted_index.International	0
cited_by_percentile_year.max	98
cited_by_percentile_year.min	89
countries_distinct_count	2
institutions_distinct_count	3
sustainable_development_goals[0].id	https://metadata.un.org/sdg/3
sustainable_development_goals[0].score	0.8500000238418579
sustainable_development_goals[0].display_name	Good health and well-being
citation_normalized_percentile.value	0.94504447
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	True