---
_id: '10906'
abstract:
- lang: eng
text: HSF(C) is a tool that automates verification of safety and liveness properties
for C programs. This paper describes the verification approach taken by HSF(C)
and provides instructions on how to install and use the tool.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Sergey
full_name: Grebenshchikov, Sergey
last_name: Grebenshchikov
- first_name: Ashutosh
full_name: Gupta, Ashutosh
id: 335E5684-F248-11E8-B48F-1D18A9856A87
last_name: Gupta
- first_name: Nuno P.
full_name: Lopes, Nuno P.
last_name: Lopes
- first_name: Corneliu
full_name: Popeea, Corneliu
last_name: Popeea
- first_name: Andrey
full_name: Rybalchenko, Andrey
last_name: Rybalchenko
citation:
ama: 'Grebenshchikov S, Gupta A, Lopes NP, Popeea C, Rybalchenko A. HSF(C): A software
verifier based on Horn clauses. In: Flanagan C, König B, eds. Tools and Algorithms
for the Construction and Analysis of Systems. Vol 7214. LNCS. Berlin, Heidelberg:
Springer; 2012:549-551. doi:10.1007/978-3-642-28756-5_46'
apa: 'Grebenshchikov, S., Gupta, A., Lopes, N. P., Popeea, C., & Rybalchenko,
A. (2012). HSF(C): A software verifier based on Horn clauses. In C. Flanagan &
B. König (Eds.), Tools and Algorithms for the Construction and Analysis of
Systems (Vol. 7214, pp. 549–551). Berlin, Heidelberg: Springer. https://doi.org/10.1007/978-3-642-28756-5_46'
chicago: 'Grebenshchikov, Sergey, Ashutosh Gupta, Nuno P. Lopes, Corneliu Popeea,
and Andrey Rybalchenko. “HSF(C): A Software Verifier Based on Horn Clauses.” In
Tools and Algorithms for the Construction and Analysis of Systems, edited
by Cormac Flanagan and Barbara König, 7214:549–51. LNCS. Berlin, Heidelberg: Springer,
2012. https://doi.org/10.1007/978-3-642-28756-5_46.'
ieee: 'S. Grebenshchikov, A. Gupta, N. P. Lopes, C. Popeea, and A. Rybalchenko,
“HSF(C): A software verifier based on Horn clauses,” in Tools and Algorithms
for the Construction and Analysis of Systems, Tallinn, Estonia, 2012, vol.
7214, pp. 549–551.'
ista: 'Grebenshchikov S, Gupta A, Lopes NP, Popeea C, Rybalchenko A. 2012. HSF(C):
A software verifier based on Horn clauses. Tools and Algorithms for the Construction
and Analysis of Systems. TACAS: Tools and Algorithms for the Construction and
Analysis of SystemsLNCS, LNCS, vol. 7214, 549–551.'
mla: 'Grebenshchikov, Sergey, et al. “HSF(C): A Software Verifier Based on Horn
Clauses.” Tools and Algorithms for the Construction and Analysis of Systems,
edited by Cormac Flanagan and Barbara König, vol. 7214, Springer, 2012, pp. 549–51,
doi:10.1007/978-3-642-28756-5_46.'
short: S. Grebenshchikov, A. Gupta, N.P. Lopes, C. Popeea, A. Rybalchenko, in:,
C. Flanagan, B. König (Eds.), Tools and Algorithms for the Construction and Analysis
of Systems, Springer, Berlin, Heidelberg, 2012, pp. 549–551.
conference:
end_date: 2012-04-01
location: Tallinn, Estonia
name: 'TACAS: Tools and Algorithms for the Construction and Analysis of Systems'
start_date: 2012-03-24
date_created: 2022-03-21T08:03:30Z
date_published: 2012-04-01T00:00:00Z
date_updated: 2023-09-05T14:09:54Z
day: '01'
department:
- _id: ToHe
doi: 10.1007/978-3-642-28756-5_46
editor:
- first_name: Cormac
full_name: Flanagan, Cormac
last_name: Flanagan
- first_name: Barbara
full_name: König, Barbara
last_name: König
intvolume: ' 7214'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1007/978-3-642-28756-5_46
month: '04'
oa: 1
oa_version: Published Version
page: 549-551
place: Berlin, Heidelberg
publication: Tools and Algorithms for the Construction and Analysis of Systems
publication_identifier:
eisbn:
- '9783642287565'
eissn:
- 1611-3349
isbn:
- '9783642287558'
issn:
- 0302-9743
publication_status: published
publisher: Springer
quality_controlled: '1'
scopus_import: '1'
series_title: LNCS
status: public
title: 'HSF(C): A software verifier based on Horn clauses'
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 7214
year: '2012'
...
---
_id: '11795'
abstract:
- lang: eng
text: "We study multiple keyword sponsored search auctions with budgets. Each keyword
has multiple ad slots with a click-through rate. The bidders have additive valuations,
which are linear in the click-through rates, and budgets, which are restricting
their overall payments. Additionally, the number of slots per keyword assigned
to a bidder is bounded.\r\n\r\nWe show the following results: (1) We give the
first mechanism for multiple keywords, where click-through rates differ among
slots. Our mechanism is incentive compatible in expectation, individually rational
in expectation, and Pareto optimal. (2) We study the combinatorial setting, where
each bidder is only interested in a subset of the keywords. We give an incentive
compatible, individually rational, Pareto optimal, and deterministic mechanism
for identical click-through rates. (3) We give an impossibility result for incentive
compatible, individually rational, Pareto optimal, and deterministic mechanisms
for bidders with diminishing marginal valuations."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Riccardo
full_name: Colini-Baldeschi, Riccardo
last_name: Colini-Baldeschi
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Stefano
full_name: Leonardi, Stefano
last_name: Leonardi
- first_name: Martin
full_name: Starnberger, Martin
last_name: Starnberger
citation:
ama: 'Colini-Baldeschi R, Henzinger MH, Leonardi S, Starnberger M. On multiple keyword
sponsored search auctions with budgets. In: 39th International Colloquium on
Automata, Languages, and Programming. Vol 7392. Springer Nature; 2012:1–12.
doi:10.1007/978-3-642-31585-5_1'
apa: 'Colini-Baldeschi, R., Henzinger, M. H., Leonardi, S., & Starnberger, M.
(2012). On multiple keyword sponsored search auctions with budgets. In 39th
International Colloquium on Automata, Languages, and Programming (Vol. 7392,
pp. 1–12). Warwick, United Kingdom: Springer Nature. https://doi.org/10.1007/978-3-642-31585-5_1'
chicago: Colini-Baldeschi, Riccardo, Monika H Henzinger, Stefano Leonardi, and Martin
Starnberger. “On Multiple Keyword Sponsored Search Auctions with Budgets.” In
39th International Colloquium on Automata, Languages, and Programming,
7392:1–12. Springer Nature, 2012. https://doi.org/10.1007/978-3-642-31585-5_1.
ieee: R. Colini-Baldeschi, M. H. Henzinger, S. Leonardi, and M. Starnberger, “On
multiple keyword sponsored search auctions with budgets,” in 39th International
Colloquium on Automata, Languages, and Programming, Warwick, United Kingdom,
2012, vol. 7392, pp. 1–12.
ista: 'Colini-Baldeschi R, Henzinger MH, Leonardi S, Starnberger M. 2012. On multiple
keyword sponsored search auctions with budgets. 39th International Colloquium
on Automata, Languages, and Programming. ICALP: International Colloquium on Automata,
Languages, and Programming, LNCS, vol. 7392, 1–12.'
mla: Colini-Baldeschi, Riccardo, et al. “On Multiple Keyword Sponsored Search Auctions
with Budgets.” 39th International Colloquium on Automata, Languages, and Programming,
vol. 7392, Springer Nature, 2012, pp. 1–12, doi:10.1007/978-3-642-31585-5_1.
short: R. Colini-Baldeschi, M.H. Henzinger, S. Leonardi, M. Starnberger, in:, 39th
International Colloquium on Automata, Languages, and Programming, Springer Nature,
2012, pp. 1–12.
conference:
end_date: 2012-07-13
location: Warwick, United Kingdom
name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
start_date: 2012-07-09
date_created: 2022-08-11T11:46:51Z
date_published: 2012-07-01T00:00:00Z
date_updated: 2023-02-21T16:28:31Z
day: '01'
doi: 10.1007/978-3-642-31585-5_1
extern: '1'
intvolume: ' 7392'
language:
- iso: eng
month: '07'
oa_version: None
page: 1–12
publication: 39th International Colloquium on Automata, Languages, and Programming
publication_identifier:
isbn:
- '9783642315848'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '11795'
relation: later_version
status: public
scopus_import: '1'
status: public
title: On multiple keyword sponsored search auctions with budgets
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7392
year: '2012'
...
---
_id: '5745'
article_processing_charge: No
author:
- first_name: Ashutosh
full_name: Gupta, Ashutosh
last_name: Gupta
citation:
ama: 'Gupta A. Improved Single Pass Algorithms for Resolution Proof Reduction. In:
Automated Technology for Verification and Analysis. Vol 7561. LNCS. Berlin,
Heidelberg: Springer Berlin Heidelberg; 2012:107-121. doi:10.1007/978-3-642-33386-6_10'
apa: 'Gupta, A. (2012). Improved Single Pass Algorithms for Resolution Proof Reduction.
In Automated Technology for Verification and Analysis (Vol. 7561, pp. 107–121).
Berlin, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-33386-6_10'
chicago: 'Gupta, Ashutosh. “Improved Single Pass Algorithms for Resolution Proof
Reduction.” In Automated Technology for Verification and Analysis, 7561:107–21.
LNCS. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. https://doi.org/10.1007/978-3-642-33386-6_10.'
ieee: 'A. Gupta, “Improved Single Pass Algorithms for Resolution Proof Reduction,”
in Automated Technology for Verification and Analysis, vol. 7561, Berlin,
Heidelberg: Springer Berlin Heidelberg, 2012, pp. 107–121.'
ista: 'Gupta A. 2012.Improved Single Pass Algorithms for Resolution Proof Reduction.
In: Automated Technology for Verification and Analysis. vol. 7561, 107–121.'
mla: Gupta, Ashutosh. “Improved Single Pass Algorithms for Resolution Proof Reduction.”
Automated Technology for Verification and Analysis, vol. 7561, Springer
Berlin Heidelberg, 2012, pp. 107–21, doi:10.1007/978-3-642-33386-6_10.
short: A. Gupta, in:, Automated Technology for Verification and Analysis, Springer
Berlin Heidelberg, Berlin, Heidelberg, 2012, pp. 107–121.
conference:
end_date: 2012-10-06
location: Thiruvananthapuram, Kerala, India
name: ATVA 2012
start_date: 2012-10-03
date_created: 2018-12-18T13:01:46Z
date_published: 2012-01-01T00:00:00Z
date_updated: 2023-09-05T14:15:29Z
ddc:
- '005'
department:
- _id: ToHe
doi: 10.1007/978-3-642-33386-6_10
ec_funded: 1
file:
- access_level: open_access
checksum: 68415837a315de3cc4d120f6019d752c
content_type: application/pdf
creator: dernst
date_created: 2018-12-18T13:07:35Z
date_updated: 2020-07-14T12:47:10Z
file_id: '5746'
file_name: 2012_ATVA_Gupta.pdf
file_size: 465502
relation: main_file
file_date_updated: 2020-07-14T12:47:10Z
has_accepted_license: '1'
intvolume: ' 7561'
language:
- iso: eng
oa: 1
oa_version: None
page: 107-121
place: Berlin, Heidelberg
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
publication: Automated Technology for Verification and Analysis
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783642333859'
- '9783642333866'
issn:
- 0302-9743
publication_status: published
publisher: Springer Berlin Heidelberg
pubrep_id: '180'
quality_controlled: '1'
series_title: LNCS
status: public
title: Improved Single Pass Algorithms for Resolution Proof Reduction
type: book_chapter
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 7561
year: '2012'
...
---
_id: '10907'
abstract:
- lang: eng
text: This paper presents a method to create a model of an articulated object using
the planar motion in an initialization video. The model consists of rigid parts
connected by points of articulation. The rigid parts are described by the positions
of salient feature-points tracked throughout the video. Following a filtering
step that identifies points that belong to different objects, rigid parts are
found by a grouping process in a graph pyramid. Valid articulation points are
selected by verifying multiple hypotheses for each pair of parts.
acknowledgement: This work has been partially supported by the Austrian Science Fund
under grants S9103-N13 and P18716-N13.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Nicole M.
full_name: Artner, Nicole M.
last_name: Artner
- first_name: Adrian
full_name: Ion, Adrian
id: 29F89302-F248-11E8-B48F-1D18A9856A87
last_name: Ion
- first_name: Walter G.
full_name: Kropatsch, Walter G.
last_name: Kropatsch
citation:
ama: 'Artner NM, Ion A, Kropatsch WG. Spatio-temporal extraction of articulated
models in a graph pyramid. In: Jiang X, Ferrer M, Torsello A, eds. Graph-Based
Representations in Pattern Recognition. Vol 6658. LNIP. Berlin, Heidelberg:
Springer; 2011:215-224. doi:10.1007/978-3-642-20844-7_22'
apa: 'Artner, N. M., Ion, A., & Kropatsch, W. G. (2011). Spatio-temporal extraction
of articulated models in a graph pyramid. In X. Jiang, M. Ferrer, & A. Torsello
(Eds.), Graph-Based Representations in Pattern Recognition (Vol. 6658,
pp. 215–224). Berlin, Heidelberg: Springer. https://doi.org/10.1007/978-3-642-20844-7_22'
chicago: 'Artner, Nicole M., Adrian Ion, and Walter G. Kropatsch. “Spatio-Temporal
Extraction of Articulated Models in a Graph Pyramid.” In Graph-Based Representations
in Pattern Recognition, edited by Xiaoyi Jiang, Miquel Ferrer, and Andrea
Torsello, 6658:215–24. LNIP. Berlin, Heidelberg: Springer, 2011. https://doi.org/10.1007/978-3-642-20844-7_22.'
ieee: N. M. Artner, A. Ion, and W. G. Kropatsch, “Spatio-temporal extraction of
articulated models in a graph pyramid,” in Graph-Based Representations in Pattern
Recognition, Münster, Germany, 2011, vol. 6658, pp. 215–224.
ista: 'Artner NM, Ion A, Kropatsch WG. 2011. Spatio-temporal extraction of articulated
models in a graph pyramid. Graph-Based Representations in Pattern Recognition.
GbRPR: Graph-based Representations in Pattern RecognitionLNIP, LNCS, vol. 6658,
215–224.'
mla: Artner, Nicole M., et al. “Spatio-Temporal Extraction of Articulated Models
in a Graph Pyramid.” Graph-Based Representations in Pattern Recognition,
edited by Xiaoyi Jiang et al., vol. 6658, Springer, 2011, pp. 215–24, doi:10.1007/978-3-642-20844-7_22.
short: N.M. Artner, A. Ion, W.G. Kropatsch, in:, X. Jiang, M. Ferrer, A. Torsello
(Eds.), Graph-Based Representations in Pattern Recognition, Springer, Berlin,
Heidelberg, 2011, pp. 215–224.
conference:
end_date: 2011-05-20
location: Münster, Germany
name: 'GbRPR: Graph-based Representations in Pattern Recognition'
start_date: 2011-05-18
date_created: 2022-03-21T08:08:35Z
date_published: 2011-06-01T00:00:00Z
date_updated: 2023-09-05T14:10:15Z
day: '01'
department:
- _id: HeEd
doi: 10.1007/978-3-642-20844-7_22
editor:
- first_name: Xiaoyi
full_name: Jiang, Xiaoyi
last_name: Jiang
- first_name: Miquel
full_name: Ferrer, Miquel
last_name: Ferrer
- first_name: Andrea
full_name: Torsello, Andrea
last_name: Torsello
intvolume: ' 6658'
language:
- iso: eng
month: '06'
oa_version: None
page: 215-224
place: Berlin, Heidelberg
publication: Graph-Based Representations in Pattern Recognition
publication_identifier:
eisbn:
- '9783642208447'
eissn:
- 1611-3349
isbn:
- '9783642208430'
issn:
- 0302-9743
publication_status: published
publisher: Springer
quality_controlled: '1'
scopus_import: '1'
series_title: LNIP
status: public
title: Spatio-temporal extraction of articulated models in a graph pyramid
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 6658
year: '2011'
...
---
_id: '10908'
abstract:
- lang: eng
text: We present ABC, a software tool for automatically computing symbolic upper
bounds on the number of iterations of nested program loops. The system combines
static analysis of programs with symbolic summation techniques to derive loop
invariant relations between program variables. Iteration bounds are obtained from
the inferred invariants, by replacing variables with bounds on their greatest
values. We have successfully applied ABC to a large number of examples. The derived
symbolic bounds express non-trivial polynomial relations over loop variables.
We also report on results to automatically infer symbolic expressions over harmonic
numbers as upper bounds on loop iteration counts.
acknowledgement: This work was supported in part by the Swiss NSF. The fourth author
is supported by an FWF Hertha Firnberg Research grant (T425-N23).
article_processing_charge: No
author:
- first_name: Régis
full_name: Blanc, Régis
last_name: Blanc
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
- first_name: Thibaud
full_name: Hottelier, Thibaud
last_name: Hottelier
- first_name: Laura
full_name: Kovács, Laura
last_name: Kovács
citation:
ama: 'Blanc R, Henzinger TA, Hottelier T, Kovács L. ABC: Algebraic Bound Computation
for loops. In: Clarke EM, Voronkov A, eds. Logic for Programming, Artificial
Intelligence, and Reasoning. Vol 6355. LNCS. Berlin, Heidelberg: Springer
Nature; 2010:103-118. doi:10.1007/978-3-642-17511-4_7'
apa: 'Blanc, R., Henzinger, T. A., Hottelier, T., & Kovács, L. (2010). ABC:
Algebraic Bound Computation for loops. In E. M. Clarke & A. Voronkov (Eds.),
Logic for Programming, Artificial Intelligence, and Reasoning (Vol. 6355,
pp. 103–118). Berlin, Heidelberg: Springer Nature. https://doi.org/10.1007/978-3-642-17511-4_7'
chicago: 'Blanc, Régis, Thomas A Henzinger, Thibaud Hottelier, and Laura Kovács.
“ABC: Algebraic Bound Computation for Loops.” In Logic for Programming, Artificial
Intelligence, and Reasoning, edited by Edmund M Clarke and Andrei Voronkov,
6355:103–18. LNCS. Berlin, Heidelberg: Springer Nature, 2010. https://doi.org/10.1007/978-3-642-17511-4_7.'
ieee: 'R. Blanc, T. A. Henzinger, T. Hottelier, and L. Kovács, “ABC: Algebraic Bound
Computation for loops,” in Logic for Programming, Artificial Intelligence,
and Reasoning, Dakar, Senegal, 2010, vol. 6355, pp. 103–118.'
ista: 'Blanc R, Henzinger TA, Hottelier T, Kovács L. 2010. ABC: Algebraic Bound
Computation for loops. Logic for Programming, Artificial Intelligence, and Reasoning.
LPAR: Conference on Logic for Programming, Artificial Intelligence and ReasoningLNCS
vol. 6355, 103–118.'
mla: 'Blanc, Régis, et al. “ABC: Algebraic Bound Computation for Loops.” Logic
for Programming, Artificial Intelligence, and Reasoning, edited by Edmund
M Clarke and Andrei Voronkov, vol. 6355, Springer Nature, 2010, pp. 103–18, doi:10.1007/978-3-642-17511-4_7.'
short: R. Blanc, T.A. Henzinger, T. Hottelier, L. Kovács, in:, E.M. Clarke, A. Voronkov
(Eds.), Logic for Programming, Artificial Intelligence, and Reasoning, Springer
Nature, Berlin, Heidelberg, 2010, pp. 103–118.
conference:
end_date: 2010-05-01
location: Dakar, Senegal
name: 'LPAR: Conference on Logic for Programming, Artificial Intelligence and Reasoning'
start_date: 2010-04-25
date_created: 2022-03-21T08:14:35Z
date_published: 2010-05-01T00:00:00Z
date_updated: 2022-06-13T07:44:21Z
day: '01'
department:
- _id: ToHe
doi: 10.1007/978-3-642-17511-4_7
editor:
- first_name: Edmund M
full_name: Clarke, Edmund M
last_name: Clarke
- first_name: Andrei
full_name: Voronkov, Andrei
last_name: Voronkov
intvolume: ' 6355'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://infoscience.epfl.ch/record/186096
month: '05'
oa: 1
oa_version: Submitted Version
page: 103-118
place: Berlin, Heidelberg
publication: Logic for Programming, Artificial Intelligence, and Reasoning
publication_identifier:
eisbn:
- '9783642175114'
eissn:
- 1611-3349
isbn:
- '9783642175107'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
series_title: LNCS
status: public
title: 'ABC: Algebraic Bound Computation for loops'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 6355
year: '2010'
...
---
_id: '5940'
article_processing_charge: No
author:
- first_name: Gabriel
full_name: Juhás, Gabriel
last_name: Juhás
- first_name: Igor
full_name: Kazlov, Igor
id: 4A997E50-F248-11E8-B48F-1D18A9856A87
last_name: Kazlov
- first_name: Ana
full_name: Juhásová, Ana
last_name: Juhásová
citation:
ama: 'Juhás G, Kazlov I, Juhásová A. Instance Deadlock: A Mystery behind Frozen
Programs. In: Applications and Theory of Petri Nets. Berlin, Heidelberg:
Springer Berlin Heidelberg; 2010:1-17. doi:10.1007/978-3-642-13675-7_1'
apa: 'Juhás, G., Kazlov, I., & Juhásová, A. (2010). Instance Deadlock: A Mystery
behind Frozen Programs. In Applications and Theory of Petri Nets (pp. 1–17).
Berlin, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-13675-7_1'
chicago: 'Juhás, Gabriel, Igor Kazlov, and Ana Juhásová. “Instance Deadlock: A Mystery
behind Frozen Programs.” In Applications and Theory of Petri Nets, 1–17.
Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. https://doi.org/10.1007/978-3-642-13675-7_1.'
ieee: 'G. Juhás, I. Kazlov, and A. Juhásová, “Instance Deadlock: A Mystery behind
Frozen Programs,” in Applications and Theory of Petri Nets, Berlin, Heidelberg:
Springer Berlin Heidelberg, 2010, pp. 1–17.'
ista: 'Juhás G, Kazlov I, Juhásová A. 2010.Instance Deadlock: A Mystery behind Frozen
Programs. In: Applications and Theory of Petri Nets. , 1–17.'
mla: 'Juhás, Gabriel, et al. “Instance Deadlock: A Mystery behind Frozen Programs.”
Applications and Theory of Petri Nets, Springer Berlin Heidelberg, 2010,
pp. 1–17, doi:10.1007/978-3-642-13675-7_1.'
short: G. Juhás, I. Kazlov, A. Juhásová, in:, Applications and Theory of Petri Nets,
Springer Berlin Heidelberg, Berlin, Heidelberg, 2010, pp. 1–17.
date_created: 2019-02-08T09:33:41Z
date_published: 2010-01-01T00:00:00Z
date_updated: 2022-04-01T13:45:24Z
doi: 10.1007/978-3-642-13675-7_1
extern: '1'
language:
- iso: eng
oa_version: None
page: 1-17
place: Berlin, Heidelberg
publication: Applications and Theory of Petri Nets
publication_identifier:
isbn:
- '9783642136740'
- '9783642136757'
issn:
- 0302-9743
- 1611-3349
publication_status: published
publisher: Springer Berlin Heidelberg
status: public
title: 'Instance Deadlock: A Mystery behind Frozen Programs'
type: book_chapter
user_id: 4A997E50-F248-11E8-B48F-1D18A9856A87
year: '2010'
...
---
_id: '11800'
abstract:
- lang: eng
text: "Web search engines have emerged as one of the central applications on the
Internet. In fact, search has become one of the most important activities that
people engage in on the the Internet. Even beyond becoming the number one source
of information, a growing number of businesses are depending on web search engines
for customer acquisition.\r\n\r\nThe first generation of web search engines used
text-only retrieval techniques. Google revolutionized the field by deploying the
PageRank technology – an eigenvector-based analysis of the hyperlink structure
– to analyze the web in order to produce relevant results. Moving forward, our
goal is to achieve a better understanding of a page with a view towards producing
even more relevant results."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: 'Henzinger MH. The past, present, and future of web search engines. In: 31st
International Colloquium on Automata, Languages and Programming. Vol 3142.
Springer Nature; 2004:3. doi:10.1007/978-3-540-27836-8_2'
apa: 'Henzinger, M. H. (2004). The past, present, and future of web search engines.
In 31st International Colloquium on Automata, Languages and Programming
(Vol. 3142, p. 3). Turku, Finland: Springer Nature. https://doi.org/10.1007/978-3-540-27836-8_2'
chicago: Henzinger, Monika H. “The Past, Present, and Future of Web Search Engines.”
In 31st International Colloquium on Automata, Languages and Programming,
3142:3. Springer Nature, 2004. https://doi.org/10.1007/978-3-540-27836-8_2.
ieee: M. H. Henzinger, “The past, present, and future of web search engines,” in
31st International Colloquium on Automata, Languages and Programming, Turku,
Finland, 2004, vol. 3142, p. 3.
ista: 'Henzinger MH. 2004. The past, present, and future of web search engines.
31st International Colloquium on Automata, Languages and Programming. ICALP: International
Colloquium on Automata, Languages, and Programming, LNCS, vol. 3142, 3.'
mla: Henzinger, Monika H. “The Past, Present, and Future of Web Search Engines.”
31st International Colloquium on Automata, Languages and Programming, vol.
3142, Springer Nature, 2004, p. 3, doi:10.1007/978-3-540-27836-8_2.
short: M.H. Henzinger, in:, 31st International Colloquium on Automata, Languages
and Programming, Springer Nature, 2004, p. 3.
conference:
end_date: 2004-07-16
location: Turku, Finland
name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
start_date: 2004-07-12
date_created: 2022-08-11T12:38:58Z
date_published: 2004-07-01T00:00:00Z
date_updated: 2023-02-13T11:45:25Z
day: '01'
doi: 10.1007/978-3-540-27836-8_2
extern: '1'
intvolume: ' 3142'
language:
- iso: eng
month: '07'
oa_version: None
page: '3'
publication: 31st International Colloquium on Automata, Languages and Programming
publication_identifier:
eissn:
- 1611-3349
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: The past, present, and future of web search engines
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 3142
year: '2004'
...
---
_id: '11801'
abstract:
- lang: eng
text: "Web search engines have emerged as one of the central applications on the
internet. In fact, search has become one of the most important activities that
people engage in on the Internet. Even beyond becoming the number one source of
information, a growing number of businesses are depending on web search engines
for customer acquisition. In this talk I will brief review the history of web
search engines: The first generation of web search engines used text-only retrieval
techniques. Google revolutionized the field by deploying the PageRank technology
– an eigenvector-based analysis of the hyperlink structure- to analyze the web
in order to produce relevant results. Moving forward, our goal is to achieve a
better understanding of a page with a view towards producing even more relevant
results.\r\n\r\nGoogle is powered by a large number of PCs. Using this infrastructure
and striving to be as efficient as possible poses challenging systems problems
but also various algorithmic challenges. I will discuss some of them in my talk."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: 'Henzinger MH. Algorithmic aspects of web search engines. In: 2th Annual
European Symposium on Algorithms. Vol 3221. Springer Nature; 2004:3. doi:10.1007/978-3-540-30140-0_2'
apa: 'Henzinger, M. H. (2004). Algorithmic aspects of web search engines. In 2th
Annual European Symposium on Algorithms (Vol. 3221, p. 3). Bergen, Norway:
Springer Nature. https://doi.org/10.1007/978-3-540-30140-0_2'
chicago: Henzinger, Monika H. “Algorithmic Aspects of Web Search Engines.” In 2th
Annual European Symposium on Algorithms, 3221:3. Springer Nature, 2004. https://doi.org/10.1007/978-3-540-30140-0_2.
ieee: M. H. Henzinger, “Algorithmic aspects of web search engines,” in 2th Annual
European Symposium on Algorithms, Bergen, Norway, 2004, vol. 3221, p. 3.
ista: 'Henzinger MH. 2004. Algorithmic aspects of web search engines. 2th Annual
European Symposium on Algorithms. ESA: European Symposium on Algorithms, LNCS,
vol. 3221, 3.'
mla: Henzinger, Monika H. “Algorithmic Aspects of Web Search Engines.” 2th Annual
European Symposium on Algorithms, vol. 3221, Springer Nature, 2004, p. 3,
doi:10.1007/978-3-540-30140-0_2.
short: M.H. Henzinger, in:, 2th Annual European Symposium on Algorithms, Springer
Nature, 2004, p. 3.
conference:
end_date: 2004-09-17
location: Bergen, Norway
name: 'ESA: European Symposium on Algorithms'
start_date: 2004-09-14
date_created: 2022-08-11T13:18:05Z
date_published: 2004-09-01T00:00:00Z
date_updated: 2023-02-13T11:47:26Z
day: '01'
doi: 10.1007/978-3-540-30140-0_2
extern: '1'
intvolume: ' 3221'
language:
- iso: eng
month: '09'
oa_version: None
page: '3'
publication: 2th Annual European Symposium on Algorithms
publication_identifier:
eissn:
- 1611-3349
isbn:
- ' 3540230254'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Algorithmic aspects of web search engines
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 3221
year: '2004'
...
---
_id: '11802'
abstract:
- lang: eng
text: In this paper we survey algorithmic aspects of Web information retrieval.
As an example, we discuss ranking of search engine results using connectivity
analysis.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: 'Henzinger MH. Web information retrieval - an algorithmic perspective. In:
8th Annual European Symposium on Algorithms. Vol 1879. Springer Nature;
2000:1–8. doi:10.1007/3-540-45253-2_1'
apa: 'Henzinger, M. H. (2000). Web information retrieval - an algorithmic perspective.
In 8th Annual European Symposium on Algorithms (Vol. 1879, pp. 1–8). Saarbrücken,
Germany: Springer Nature. https://doi.org/10.1007/3-540-45253-2_1'
chicago: Henzinger, Monika H. “Web Information Retrieval - an Algorithmic Perspective.”
In 8th Annual European Symposium on Algorithms, 1879:1–8. Springer Nature,
2000. https://doi.org/10.1007/3-540-45253-2_1.
ieee: M. H. Henzinger, “Web information retrieval - an algorithmic perspective,”
in 8th Annual European Symposium on Algorithms, Saarbrücken, Germany, 2000,
vol. 1879, pp. 1–8.
ista: 'Henzinger MH. 2000. Web information retrieval - an algorithmic perspective.
8th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms,
LNCS, vol. 1879, 1–8.'
mla: Henzinger, Monika H. “Web Information Retrieval - an Algorithmic Perspective.”
8th Annual European Symposium on Algorithms, vol. 1879, Springer Nature,
2000, pp. 1–8, doi:10.1007/3-540-45253-2_1.
short: M.H. Henzinger, in:, 8th Annual European Symposium on Algorithms, Springer
Nature, 2000, pp. 1–8.
conference:
end_date: 2000-09-08
location: Saarbrücken, Germany
name: 'ESA: European Symposium on Algorithms'
start_date: 2000-09-05
date_created: 2022-08-11T13:25:07Z
date_published: 2000-09-01T00:00:00Z
date_updated: 2023-02-13T12:08:21Z
day: '01'
doi: 10.1007/3-540-45253-2_1
extern: '1'
intvolume: ' 1879'
language:
- iso: eng
month: '09'
oa_version: None
page: 1–8
publication: 8th Annual European Symposium on Algorithms
publication_identifier:
eisbn:
- '9783540452539'
eissn:
- 1611-3349
isbn:
- '9783540410041'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Web information retrieval - an algorithmic perspective
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 1879
year: '2000'
...
---
_id: '11803'
abstract:
- lang: eng
text: We present the first fully dynamic algorithm for maintaining a minimum spanning
tree in time o(√n) per operation. To be precise, the algorithm uses O(n 1/3 log
n) amortized time per update operation. The algorithm is fairly simple and deterministic.
An immediate consequence is the first fully dynamic deterministic algorithm for
maintaining connectivity and, bipartiteness in amortized time O(n 1/3 log n) per
update, with O(1) worst case time per query.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Valerie
full_name: King, Valerie
last_name: King
citation:
ama: 'Henzinger MH, King V. Maintaining minimum spanning trees in dynamic graphs.
In: 24th International Colloquium on Automata, Languages and Programming.
Vol 1256. Springer Nature; 1997:594–604. doi:10.1007/3-540-63165-8_214'
apa: 'Henzinger, M. H., & King, V. (1997). Maintaining minimum spanning trees
in dynamic graphs. In 24th International Colloquium on Automata, Languages
and Programming (Vol. 1256, pp. 594–604). Bologna, Italy: Springer Nature.
https://doi.org/10.1007/3-540-63165-8_214'
chicago: Henzinger, Monika H, and Valerie King. “Maintaining Minimum Spanning Trees
in Dynamic Graphs.” In 24th International Colloquium on Automata, Languages
and Programming, 1256:594–604. Springer Nature, 1997. https://doi.org/10.1007/3-540-63165-8_214.
ieee: M. H. Henzinger and V. King, “Maintaining minimum spanning trees in dynamic
graphs,” in 24th International Colloquium on Automata, Languages and Programming,
Bologna, Italy, 1997, vol. 1256, pp. 594–604.
ista: 'Henzinger MH, King V. 1997. Maintaining minimum spanning trees in dynamic
graphs. 24th International Colloquium on Automata, Languages and Programming.
ICALP: International Colloquium on Automata, Languages, and Programming, LNCS,
vol. 1256, 594–604.'
mla: Henzinger, Monika H., and Valerie King. “Maintaining Minimum Spanning Trees
in Dynamic Graphs.” 24th International Colloquium on Automata, Languages and
Programming, vol. 1256, Springer Nature, 1997, pp. 594–604, doi:10.1007/3-540-63165-8_214.
short: M.H. Henzinger, V. King, in:, 24th International Colloquium on Automata,
Languages and Programming, Springer Nature, 1997, pp. 594–604.
conference:
end_date: 1997-07-11
location: Bologna, Italy
name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
start_date: 1997-07-07
date_created: 2022-08-11T13:35:06Z
date_published: 1997-07-01T00:00:00Z
date_updated: 2023-02-14T07:49:03Z
day: '01'
doi: 10.1007/3-540-63165-8_214
extern: '1'
intvolume: ' 1256'
language:
- iso: eng
month: '07'
oa_version: None
page: 594–604
publication: 24th International Colloquium on Automata, Languages and Programming
publication_identifier:
eisbn:
- '9783540691945'
eissn:
- 1611-3349
isbn:
- '9783540631651'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Maintaining minimum spanning trees in dynamic graphs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 1256
year: '1997'
...
---
_id: '4612'
alternative_title:
- LNCS
article_processing_charge: No
citation:
ama: 'Alur R, Henzinger TA, Sontag ED, eds. Hybrid Systems III: Verification
and Control. Vol 1066. Berlin ; Heidelberg: Springer; 1996. doi:10.1007/BFb0020931'
apa: 'Alur, R., Henzinger, T. A., & Sontag, E. D. (Eds.). (1996). Hybrid
Systems III: Verification and Control (Vol. 1066). Berlin ; Heidelberg: Springer.
https://doi.org/10.1007/BFb0020931'
chicago: 'Alur, Rajeev, Thomas A Henzinger, and Eduardo D Sontag, eds. Hybrid
Systems III: Verification and Control. Vol. 1066. Lecture Notes in Computer
Science. Berlin ; Heidelberg: Springer, 1996. https://doi.org/10.1007/BFb0020931.'
ieee: 'R. Alur, T. A. Henzinger, and E. D. Sontag, Eds., Hybrid Systems III:
Verification and Control, vol. 1066. Berlin ; Heidelberg: Springer, 1996.'
ista: 'Alur R, Henzinger TA, Sontag ED eds. 1996. Hybrid Systems III: Verification
and Control, Berlin ; Heidelberg: Springer, IX, 619p.'
mla: 'Alur, Rajeev, et al., editors. Hybrid Systems III: Verification and Control.
Vol. 1066, Springer, 1996, doi:10.1007/BFb0020931.'
short: 'R. Alur, T.A. Henzinger, E.D. Sontag, eds., Hybrid Systems III: Verification
and Control, Springer, Berlin ; Heidelberg, 1996.'
date_created: 2018-12-11T12:09:45Z
date_published: 1996-01-01T00:00:00Z
date_updated: 2021-12-22T13:57:33Z
day: '01'
doi: 10.1007/BFb0020931
editor:
- first_name: Rajeev
full_name: Alur, Rajeev
last_name: Alur
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Eduardo D
full_name: Sontag, Eduardo D
last_name: Sontag
extern: '1'
intvolume: ' 1066'
language:
- iso: eng
month: '01'
oa_version: None
page: IX, 619
place: Berlin ; Heidelberg
publication_identifier:
isbn:
- 978-3-540-61155-4
issn:
- 0302-9743
publication_status: published
publisher: Springer
publist_id: '97'
quality_controlled: '1'
series_title: Lecture Notes in Computer Science
status: public
title: 'Hybrid Systems III: Verification and Control'
type: book_editor
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 1066
year: '1996'
...
---
_id: '11804'
abstract:
- lang: eng
text: "This paper shows how a general technique, called lock-step search, used in
dynamic graph algorithms, can be used to improve the running time of two problems
arising in program verification and communication protocol design.\r\n(1)We consider
the nonemptiness problem for Streett automata: We are given a directed graph G
= (V, E) with n = ¦V¦ and m = ¦E¦, and a collection of pairs of subsets of vertices,
called Streett pairs,〈L i , U i 〉, i = 1.k. The question is whether G has a cycle
(not necessarily simple) which, for each 1 ≤ i ≤ k, if it contains a vertex from
L i then it also contains a vertex of U i . Let b=Σ i=1..k |L i |+|U i |. The
previously best algorithm takes time O((m + b) min{n, k}). We present an algorithm
that takes time \U0001D442(\U0001D45Amin{\U0001D45A\U0001D459\U0001D45C\U0001D454\U0001D45B,‾‾‾‾‾‾√\U0001D458,\U0001D45B}+\U0001D44F\U0001D45A\U0001D456\U0001D45B{\U0001D459\U0001D45C\U0001D454\U0001D45B,\U0001D458}).\r\n(2)In
communication protocol pruning we are given a directed graph G = (V, E) with l
special vertices. The problem is to efficiently maintain the strongly-connected
components of the special vertices on a restricted set of edge deletions. Let
m i be the number of edges in the strongly connected component of the ith special
vertex. The previously best algorithm repeatedly recomputes the strongly-connected
components which leads to a running time of O(Σ i m 2i). We present an algorithm
with time \U0001D442(\U0001D459√∑\U0001D456\U0001D45A1.5\U0001D456)."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Jan Arne
full_name: Telle, Jan Arne
last_name: Telle
citation:
ama: 'Henzinger MH, Telle JA. Faster algorithms for the nonemptiness of streett
automata and for communication protocol pruning. In: 5th Scandinavian Workshop
on Algorithm Theory. Vol 1097. Springer Nature; 1996:16–27. doi:10.1007/3-540-61422-2_117'
apa: 'Henzinger, M. H., & Telle, J. A. (1996). Faster algorithms for the nonemptiness
of streett automata and for communication protocol pruning. In 5th Scandinavian
Workshop on Algorithm Theory (Vol. 1097, pp. 16–27). Reykjavik, Iceland: Springer
Nature. https://doi.org/10.1007/3-540-61422-2_117'
chicago: Henzinger, Monika H, and Jan Arne Telle. “Faster Algorithms for the Nonemptiness
of Streett Automata and for Communication Protocol Pruning.” In 5th Scandinavian
Workshop on Algorithm Theory, 1097:16–27. Springer Nature, 1996. https://doi.org/10.1007/3-540-61422-2_117.
ieee: M. H. Henzinger and J. A. Telle, “Faster algorithms for the nonemptiness of
streett automata and for communication protocol pruning,” in 5th Scandinavian
Workshop on Algorithm Theory, Reykjavik, Iceland, 1996, vol. 1097, pp. 16–27.
ista: 'Henzinger MH, Telle JA. 1996. Faster algorithms for the nonemptiness of streett
automata and for communication protocol pruning. 5th Scandinavian Workshop on
Algorithm Theory. SWAT: Scandinavian Workshop on Algorithm Theory, LNCS, vol.
1097, 16–27.'
mla: Henzinger, Monika H., and Jan Arne Telle. “Faster Algorithms for the Nonemptiness
of Streett Automata and for Communication Protocol Pruning.” 5th Scandinavian
Workshop on Algorithm Theory, vol. 1097, Springer Nature, 1996, pp. 16–27,
doi:10.1007/3-540-61422-2_117.
short: M.H. Henzinger, J.A. Telle, in:, 5th Scandinavian Workshop on Algorithm Theory,
Springer Nature, 1996, pp. 16–27.
conference:
end_date: 1996-07-05
location: Reykjavik, Iceland
name: 'SWAT: Scandinavian Workshop on Algorithm Theory'
start_date: 1996-07-03
date_created: 2022-08-11T13:42:42Z
date_published: 1996-07-01T00:00:00Z
date_updated: 2023-02-14T07:52:17Z
day: '01'
doi: 10.1007/3-540-61422-2_117
extern: '1'
intvolume: ' 1097'
language:
- iso: eng
month: '07'
oa_version: None
page: 16–27
publication: 5th Scandinavian Workshop on Algorithm Theory
publication_identifier:
eisbn:
- '9783540685296'
eissn:
- 1611-3349
isbn:
- '9783540614227'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Faster algorithms for the nonemptiness of streett automata and for communication
protocol pruning
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 1097
year: '1996'
...
---
_id: '11910'
abstract:
- lang: eng
text: "We state a new sampling lemma and use it to improve the running time of dynamic
graph algorithms.\r\n\r\nFor the dynamic connectivity problem the previously best
randomized algorithm takes expected time O(log3 n) per update, amortized over
Ω(m) updates. Using the new sampling lemma, we improve its running time to O(log2
n). There exists a lower bound in the cell probe model for the time per operation
of Ω(log n/ log log n) for this problem.\r\n\r\nSimilarly improved running times
are achieved for 2-edge connectivity, k-weight minimum spanning tree, and bipartiteness."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Mikkel
full_name: Thorup, Mikkel
last_name: Thorup
citation:
ama: 'Henzinger MH, Thorup M. Improved sampling with applications to dynamic graph
algorithms. In: 23rd International Colloquium on Automata, Languages, and Programming.
Vol 1099. Springer Nature; 1996:290-299. doi:10.1007/3-540-61440-0_136'
apa: 'Henzinger, M. H., & Thorup, M. (1996). Improved sampling with applications
to dynamic graph algorithms. In 23rd International Colloquium on Automata,
Languages, and Programming (Vol. 1099, pp. 290–299). Paderborn, Germany: Springer
Nature. https://doi.org/10.1007/3-540-61440-0_136'
chicago: Henzinger, Monika H, and Mikkel Thorup. “Improved Sampling with Applications
to Dynamic Graph Algorithms.” In 23rd International Colloquium on Automata,
Languages, and Programming, 1099:290–99. Springer Nature, 1996. https://doi.org/10.1007/3-540-61440-0_136.
ieee: M. H. Henzinger and M. Thorup, “Improved sampling with applications to dynamic
graph algorithms,” in 23rd International Colloquium on Automata, Languages,
and Programming, Paderborn, Germany, 1996, vol. 1099, pp. 290–299.
ista: 'Henzinger MH, Thorup M. 1996. Improved sampling with applications to dynamic
graph algorithms. 23rd International Colloquium on Automata, Languages, and Programming.
ICALP: International Colloquium on Automata, Languages, and Programming, LNCS,
vol. 1099, 290–299.'
mla: Henzinger, Monika H., and Mikkel Thorup. “Improved Sampling with Applications
to Dynamic Graph Algorithms.” 23rd International Colloquium on Automata, Languages,
and Programming, vol. 1099, Springer Nature, 1996, pp. 290–99, doi:10.1007/3-540-61440-0_136.
short: M.H. Henzinger, M. Thorup, in:, 23rd International Colloquium on Automata,
Languages, and Programming, Springer Nature, 1996, pp. 290–299.
conference:
end_date: 1996-07-12
location: Paderborn, Germany
name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
start_date: 1996-07-08
date_created: 2022-08-18T06:42:24Z
date_published: 1996-07-01T00:00:00Z
date_updated: 2023-02-14T07:57:14Z
day: '01'
doi: 10.1007/3-540-61440-0_136
extern: '1'
intvolume: ' 1099'
language:
- iso: eng
month: '07'
oa_version: None
page: 290-299
publication: 23rd International Colloquium on Automata, Languages, and Programming
publication_identifier:
eisbn:
- '9783540685807'
eissn:
- 1611-3349
isbn:
- '9783540614401'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Improved sampling with applications to dynamic graph algorithms
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 1099
year: '1996'
...
---
_id: '11805'
abstract:
- lang: eng
text: In this paper, we present sparse certificates for biconnectivity together
with algorithms for updating these certificates. We thus obtain fully-dynamic
algorithms for biconnectivity in graphs that run in O(√n log n log⌈m/n⌉) amortized
time per operation, where m is the number of edges and n is the number of nodes
in the graph. This improves upon the results in [11], in which algorithms were
presented running in O(√m) amortized time, and solves the open problem to find
certificates to speed up biconnectivity, as stated in [2].
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Han
full_name: Poutré, Han
last_name: Poutré
citation:
ama: 'Henzinger MH, Poutré H. Certificates and fast algorithms for biconnectivity
in fully-dynamic graphs. In: 3rd Annual European Symposium on Algorithms.
Vol 979. Springer Nature; 1995:171–184. doi:10.1007/3-540-60313-1_142'
apa: 'Henzinger, M. H., & Poutré, H. (1995). Certificates and fast algorithms
for biconnectivity in fully-dynamic graphs. In 3rd Annual European Symposium
on Algorithms (Vol. 979, pp. 171–184). Corfu, Greece: Springer Nature. https://doi.org/10.1007/3-540-60313-1_142'
chicago: Henzinger, Monika H, and Han Poutré. “Certificates and Fast Algorithms
for Biconnectivity in Fully-Dynamic Graphs.” In 3rd Annual European Symposium
on Algorithms, 979:171–184. Springer Nature, 1995. https://doi.org/10.1007/3-540-60313-1_142.
ieee: M. H. Henzinger and H. Poutré, “Certificates and fast algorithms for biconnectivity
in fully-dynamic graphs,” in 3rd Annual European Symposium on Algorithms,
Corfu, Greece, 1995, vol. 979, pp. 171–184.
ista: 'Henzinger MH, Poutré H. 1995. Certificates and fast algorithms for biconnectivity
in fully-dynamic graphs. 3rd Annual European Symposium on Algorithms. ESA: European
Symposium on Algorithms, LNCS, vol. 979, 171–184.'
mla: Henzinger, Monika H., and Han Poutré. “Certificates and Fast Algorithms for
Biconnectivity in Fully-Dynamic Graphs.” 3rd Annual European Symposium on Algorithms,
vol. 979, Springer Nature, 1995, pp. 171–184, doi:10.1007/3-540-60313-1_142.
short: M.H. Henzinger, H. Poutré, in:, 3rd Annual European Symposium on Algorithms,
Springer Nature, 1995, pp. 171–184.
conference:
end_date: 1995-09-27
location: Corfu, Greece
name: 'ESA: European Symposium on Algorithms'
start_date: 1995-09-25
date_created: 2022-08-11T14:09:52Z
date_published: 1995-09-01T00:00:00Z
date_updated: 2023-02-14T08:02:03Z
day: '01'
doi: 10.1007/3-540-60313-1_142
extern: '1'
intvolume: ' 979'
language:
- iso: eng
month: '09'
oa_version: None
page: 171–184
publication: 3rd Annual European Symposium on Algorithms
publication_identifier:
eisbn:
- '9783540449133'
eissn:
- 1611-3349
isbn:
- '9783540603139'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Certificates and fast algorithms for biconnectivity in fully-dynamic graphs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 979
year: '1995'
...
---
_id: '11806'
abstract:
- lang: eng
text: This paper presents insertions-only algorithms for maintaining the exact and
approximate size of the minimum edge cut and the minimum vertex cut of a graph.
The algorithms output the approximate or exact size k in time O(1) or O(log n)
and a cut of size k in time linear in its size. The amortized time per insertion
is O(1/ε 2) for a (2+ε)-approximation, O((log λ)((log n)/ε)2) for a (1+ε)-approximation,
and O(λ log n) for the exact size of the minimum edge cut, where n is the number
of nodes in the graph, λ is the size of the minimum cut and ε>0. The (2+ε)-approximation
algorithm and the exact algorithm are deterministic, the (1+ε)-approximation algorithm
is randomized. The algorithms are optimal in the sense that the time needed for
m insertions matches the time needed by the best static algorithm on a m-edge
graph. We also present a static 2-approximation algorithm for the size κ of the
minimum vertex cut in a graph, which takes time O(n 2 min(√n,κ)). This is a factor
of κ faster than the best algorithm for computing the exact size, which takes
time O(κ 2 n 2 +κ 3 n 1.5). We give an insertionsonly algorithm for maintaining
a (2+ε)-approximation of the minimum vertex cut with amortized insertion time
O(n(logκk)/ε).
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: 'Henzinger MH. Approximating minimum cuts under insertions. In: 22nd International
Colloquium on Automata, Languages and Programming. Vol 944. Springer Nature;
1995:280–291. doi:10.1007/3-540-60084-1_81'
apa: 'Henzinger, M. H. (1995). Approximating minimum cuts under insertions. In 22nd
International Colloquium on Automata, Languages and Programming (Vol. 944,
pp. 280–291). Szeged, Hungary: Springer Nature. https://doi.org/10.1007/3-540-60084-1_81'
chicago: Henzinger, Monika H. “Approximating Minimum Cuts under Insertions.” In
22nd International Colloquium on Automata, Languages and Programming, 944:280–291.
Springer Nature, 1995. https://doi.org/10.1007/3-540-60084-1_81.
ieee: M. H. Henzinger, “Approximating minimum cuts under insertions,” in 22nd
International Colloquium on Automata, Languages and Programming, Szeged, Hungary,
1995, vol. 944, pp. 280–291.
ista: 'Henzinger MH. 1995. Approximating minimum cuts under insertions. 22nd International
Colloquium on Automata, Languages and Programming. ICALP: International Colloquium
on Automata, Languages, and Programming, LNCS, vol. 944, 280–291.'
mla: Henzinger, Monika H. “Approximating Minimum Cuts under Insertions.” 22nd
International Colloquium on Automata, Languages and Programming, vol. 944,
Springer Nature, 1995, pp. 280–291, doi:10.1007/3-540-60084-1_81.
short: M.H. Henzinger, in:, 22nd International Colloquium on Automata, Languages
and Programming, Springer Nature, 1995, pp. 280–291.
conference:
end_date: 1995-07-14
location: Szeged, Hungary
name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
start_date: 1995-07-10
date_created: 2022-08-11T14:17:33Z
date_published: 1995-07-01T00:00:00Z
date_updated: 2023-02-14T08:09:08Z
day: '01'
doi: 10.1007/3-540-60084-1_81
extern: '1'
intvolume: ' 944'
language:
- iso: eng
month: '07'
oa_version: None
page: 280–291
publication: 22nd International Colloquium on Automata, Languages and Programming
publication_identifier:
eisbn:
- '9783540600848'
eissn:
- 1611-3349
isbn:
- '9783540494256'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Approximating minimum cuts under insertions
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 944
year: '1995'
...