4 Search Results for "Labahn, George"

Document
DOI: 10.4230/LIPIcs.SAND.2025.6
Dismountability in Temporal Cliques Revisited

Authors: Daniele Carnevale, Arnaud Casteigts, and Timothée Corsini

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract
A temporal graph is a graph whose edges are available only at certain points in time. It is temporally connected if the nodes can reach each other by paths that traverse the edges chronologically (temporal paths). Unlike static graphs, temporal graphs do not always admit small subsets of edges that preserve connectivity (temporal spanners) - there exist temporal graphs with Θ(n²) edges, all of which are critical. In the case of temporal cliques (the underlying graph is complete), spanners of size O(nlog n) are guaranteed. The original proof of this result by Casteigts et al. [ICALP 2019] combines a number of techniques, one of which is called dismountability. In a recent work, Angrick et al. [ESA 2024] simplified the proof and showed, among other things, that a one-sided version of dismountability can replace elegantly the second part of the proof. In this paper, we revisit methodically the dismountability principle. We start by characterizing the structure that a temporal clique must have if it is non 1-hop dismountable, then neither 1-hop nor 2-hop (i.e. non {1,2}-hop) dismountable, and finally non {1,2,3}-hop dismountable. It turns out that if a clique is k-hop dismountable for any other k, then it must also be {1,2,3}-hop dismountable, thus no additional structure can be obtained beyond this point. Interestingly, excluding 1-hop and 2-hop dismountability is already sufficient for reducing the spanner problem from cliques to extremally matched bicliques, where the O(nlog n) result is subsequently obtained. Put together with the strategy of Angrick et al., this entire result can now be recovered using only dismountability. An interesting by-product of our analysis is that any minimal counter-example to the existence of 4n spanners must satisfy the properties of non {1,2,3}-hop dismountable cliques. In the second part, we discuss further connections between dismountability and another technique called pivotability. In particular, we show that if a temporal clique is recursively k-hop dismountable, then it is also pivotable (and thus admits a 2n spanner, whatever k). We also study a family of labelings called full-range that forces both dismountability and pivotability. The latter gives some evidence that large lifetimes could be exploited more generally for the construction of spanners.
Cite as

Daniele Carnevale, Arnaud Casteigts, and Timothée Corsini. Dismountability in Temporal Cliques Revisited. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{carnevale_et_al:LIPIcs.SAND.2025.6,
  author =	{Carnevale, Daniele and Casteigts, Arnaud and Corsini, Timoth\'{e}e},
  title =	{{Dismountability in Temporal Cliques Revisited}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{6:1--6:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.6},
  URN =		{urn:nbn:de:0030-drops-230591},
  doi =		{10.4230/LIPIcs.SAND.2025.6},
  annote =	{Keywords: Dynamic networks, Temporal graphs, Reachability, Dismountability, Pivotability, Temporal spanners, Full-range graphs}
}
Document
DOI: 10.4230/DagRep.5.6.48
Sparse Modelling and Multi-exponential Analysis (Dagstuhl Seminar 15251)

Authors: Annie Cuyt, George Labahn, Avraham Sidi, and Wen-shin Lee

Published in: Dagstuhl Reports, Volume 5, Issue 6 (2016)

Abstract
The research fields of harmonic analysis, approximation theory and computer algebra are seemingly different domains and are studied by seemingly separated research communities. However, all of these are connected to each other in many ways. The connection between harmonic analysis and approximation theory is not accidental: several constructions among which wavelets and Fourier series, provide major insights into central problems in approximation theory. And the intimate connection between approximation theory and computer algebra exists even longer: polynomial interpolation is a long-studied and important problem in both symbolic and numeric computing, in the former to counter expression swell and in the latter to construct a simple data model. A common underlying problem statement in many applications is that of determining the number of components, and for each component the value of the frequency, damping factor, amplitude and phase in a multi-exponential model. It occurs, for instance, in magnetic resonance and infrared spectroscopy, vibration analysis, seismic data analysis, electronic odour recognition, keystroke recognition, nuclear science, music signal processing, transient detection, motor fault diagnosis, electrophysiology, drug clearance monitoring and glucose tolerance testing, to name just a few. The general technique of multi-exponential modeling is closely related to what is commonly known as the Pad/'e-Laplace method in approximation theory, and the technique of sparse interpolation in the field of computer algebra. The problem statement is also solved using a stochastic perturbation method in harmonic analysis. The problem of multi-exponential modeling is an inverse problem and therefore may be severely ill-posed, depending on the relative location of the frequencies and phases. Besides the reliability of the estimated parameters, the sparsity of the multi-exponential representation has become important. A representation is called sparse if it is a combination of only a few elements instead of all available generating elements. In sparse interpolation, the aim is to determine all the parameters from only a small amount of data samples, and with a complexity proportional to the number of terms in the representation. Despite the close connections between these fields, there is a clear lack of communication in the scientific literature. The aim of this seminar is to bring researchers together from the three mentioned fields, with scientists from the varied application domains.
Cite as

Annie Cuyt, George Labahn, Avraham Sidi, and Wen-shin Lee. Sparse Modelling and Multi-exponential Analysis (Dagstuhl Seminar 15251). In Dagstuhl Reports, Volume 5, Issue 6, pp. 48-69, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{cuyt_et_al:DagRep.5.6.48,
  author =	{Cuyt, Annie and Labahn, George and Sidi, Avraham and Lee, Wen-shin},
  title =	{{Sparse Modelling and Multi-exponential Analysis (Dagstuhl Seminar 15251)}},
  pages =	{48--69},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{5},
  number =	{6},
  editor =	{Cuyt, Annie and Labahn, George and Sidi, Avraham and Lee, Wen-shin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.6.48},
  URN =		{urn:nbn:de:0030-drops-55073},
  doi =		{10.4230/DagRep.5.6.48},
  annote =	{Keywords: Sparse Interpolation, Exponential Analysis, Signal Processing, Rational Approximation}
}
Document
DOI: 10.4230/DagSemProc.06271.11
MathBrush: An Experimental Pen-Based Math System

Authors: George Labahn, Scott MacLean, Marzouk Mirette, Ian Rutherford, and David Tausky

Published in: Dagstuhl Seminar Proceedings, Volume 6271, Challenges in Symbolic Computation Software (2006)

Abstract
It is widely believed that mathematics will be one of the major applications for Tablet PCs and other pen-based devices. In this paper we discuss many of the issues that make doing mathematics on such pen-based devices a hard task. We give a preliminary description of an experimental system, currently named MathBrush, for working with mathematics using pen-based devices. The system allows a user to enter mathematical expressions with a pen and to then do mathematical computation using a computer algebra system. The system provides a simple and easy way for users to verify the correctness of their handwritten expressions and, if needed, to correct any errors in recognition. Choosing mathematical operations is done making use of context menus, both with input and output expressions.
Cite as

George Labahn, Scott MacLean, Marzouk Mirette, Ian Rutherford, and David Tausky. MathBrush: An Experimental Pen-Based Math System. In Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings, Volume 6271, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{labahn_et_al:DagSemProc.06271.11,
  author =	{Labahn, George and MacLean, Scott and Marzouk Mirette and Rutherford, Ian and Tausky, David},
  title =	{{MathBrush: An Experimental Pen-Based Math System}},
  booktitle =	{Challenges in Symbolic Computation Software},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6271},
  editor =	{Wolfram Decker and Mike Dewar and Erich Kaltofen and Stephen Watt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06271.11},
  URN =		{urn:nbn:de:0030-drops-7733},
  doi =		{10.4230/DagSemProc.06271.11},
  annote =	{Keywords: PC Tablets, pen-based devices, computer algebra systems}
}
Document
DOI: 10.4230/DagSemProc.06271.14
Probabilistically Stable Numerical Sparse Polynomial Interpolation

Authors: Mark Giesbrecht, George Labahn, and Wen-Shin Lee

Published in: Dagstuhl Seminar Proceedings, Volume 6271, Challenges in Symbolic Computation Software (2006)

Abstract
We consider the problem of sparse interpolation of a multivariate black-box polynomial in floating-point arithmetic. That is, both the inputs and outputs of the black-box polynomial have some error, and all values are represented in standard, fixed-precision, floating-point arithmetic. By interpolating the black box evaluated at random primitive roots of unity, we give an efficient and numerically robust solution with high probability. We outline the numerical stability of our algorithm, as well as the expected conditioning achieved through randomization. Finally, we demonstrate the effectiveness of our techniques through numerical experiments.
Cite as

Mark Giesbrecht, George Labahn, and Wen-Shin Lee. Probabilistically Stable Numerical Sparse Polynomial Interpolation. In Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings, Volume 6271, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{giesbrecht_et_al:DagSemProc.06271.14,
  author =	{Giesbrecht, Mark and Labahn, George and Lee, Wen-Shin},
  title =	{{Probabilistically Stable Numerical Sparse Polynomial Interpolation}},
  booktitle =	{Challenges in Symbolic Computation Software},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6271},
  editor =	{Wolfram Decker and Mike Dewar and Erich Kaltofen and Stephen Watt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06271.14},
  URN =		{urn:nbn:de:0030-drops-7759},
  doi =		{10.4230/DagSemProc.06271.14},
  annote =	{Keywords: Symbolic-numeric computing, multivariate interpolation, sparse polynomial}
}
  • Refine by Type
  • 4 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2016
  • 2 2006

  • Refine by Author
  • 3 Labahn, George
  • 1 Carnevale, Daniele
  • 1 Casteigts, Arnaud
  • 1 Corsini, Timothée
  • 1 Cuyt, Annie
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 1 DagRep
  • 2 DagSemProc

  • Refine by Classification
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 Dismountability
  • 1 Dynamic networks
  • 1 Exponential Analysis
  • 1 Full-range graphs
  • 1 PC Tablets
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact