80 Search Results for "Lee, Wen-shin"

Volume

LIPIcs, Volume 123

29th International Symposium on Algorithms and Computation (ISAAC 2018)

ISAAC 2018, December 16-19, 2018, Jiaoxi, Yilan, Taiwan

Editors: Wen-Lian Hsu, Der-Tsai Lee, and Chung-Shou Liao

Document
DOI: 10.4230/DagRep.12.5.170
Exponential Analysis: Theoretical Progress and Technological Innovation (Dagstuhl Seminar 22221)

Authors: Annie Cuyt, Wen-shin Lee, Gerlind Plonka-Hoch, and Ferre Knaepkens

Published in: Dagstuhl Reports, Volume 12, Issue 5 (2022)

Abstract
Multi-exponential analysis might sound remote, but it touches our daily lives in many surprising ways, even if most people are unaware of how important it is. For example, a substantial amount of effort in signal processing and time series analysis is essentially dedicated to the analysis of multi-exponential functions. Multi- exponential analysis is also fundamental to several research fields and application domains that have been the subject of this Dagstuhl seminar: remote sensing, antenna design, digital imaging, all impacting some major societal or industrial challenges such as energy, transportation, space research, health and telecommunications. This Seminar connected stakeholders from seemingly separately developed fields: computational harmonic analysis, numerical linear algebra, computer algebra, nonlinear approximation theory, digital signal processing and their applications, in one and more variables.
Cite as

Annie Cuyt, Wen-shin Lee, Gerlind Plonka-Hoch, and Ferre Knaepkens. Exponential Analysis: Theoretical Progress and Technological Innovation (Dagstuhl Seminar 22221). In Dagstuhl Reports, Volume 12, Issue 5, pp. 170-187, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{cuyt_et_al:DagRep.12.5.170,
  author =	{Cuyt, Annie and Lee, Wen-shin and Plonka-Hoch, Gerlind and Knaepkens, Ferre},
  title =	{{Exponential Analysis: Theoretical Progress and Technological Innovation (Dagstuhl Seminar 22221)}},
  pages =	{170--187},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{12},
  number =	{5},
  editor =	{Cuyt, Annie and Lee, Wen-shin and Plonka-Hoch, Gerlind and Knaepkens, Ferre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.12.5.170},
  URN =		{urn:nbn:de:0030-drops-174473},
  doi =		{10.4230/DagRep.12.5.170},
  annote =	{Keywords: inverse problem, remote sensing, sparse interpolation, spectral analysis, structured matrices}
}
Document
Extended Abstract
DOI: 10.4230/OASIcs.Tokenomics.2021.10
Detecting and Quantifying Crypto Wash Trading (Extended Abstract)

Authors: Lin William Cong, Xi Li, Ke Tang, and Yang Yang

Published in: OASIcs, Volume 97, 3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)

Abstract
We introduce systematic tests exploiting robust statistical and behavioral patterns in trading to detect fake transactions on 29 cryptocurrency exchanges. Regulated exchanges feature patterns consistently observed in financial markets and nature; abnormal first-significant-digit distributions, size rounding, and transaction tail distributions on unregulated exchanges reveal rampant manipulations unlikely driven by strategy or exchange heterogeneity. We quantify the wash trading on each unregulated exchange, which averaged over 70% of the reported volume. We further document how these fabricated volumes (trillions of dollars annually) improve exchange ranking, temporarily distort prices, and relate to exchange characteristics (e.g., age and userbase), market conditions, and regulation.
Cite as

Lin William Cong, Xi Li, Ke Tang, and Yang Yang. Detecting and Quantifying Crypto Wash Trading (Extended Abstract). In 3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021). Open Access Series in Informatics (OASIcs), Volume 97, pp. 10:1-10:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{cong_et_al:OASIcs.Tokenomics.2021.10,
  author =	{Cong, Lin William and Li, Xi and Tang, Ke and Yang, Yang},
  title =	{{Detecting and Quantifying Crypto Wash Trading}},
  booktitle =	{3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)},
  pages =	{10:1--10:6},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-220-4},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{97},
  editor =	{Gramoli, Vincent and Halaburda, Hanna and Pass, Rafael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.Tokenomics.2021.10},
  URN =		{urn:nbn:de:0030-drops-159072},
  doi =		{10.4230/OASIcs.Tokenomics.2021.10},
  annote =	{Keywords: Bitcoin, Cryptocurrency, FinTech, Forensic Finance, Fraud Detection, Regulation}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.ISAAC.2018
LIPIcs, Volume 123, ISAAC'18, Complete Volume

Authors: Wen-Lian Hsu, Der-Tsai Lee, and Chung-Shou Liao

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
LIPIcs, Volume 123, ISAAC'18, Complete Volume
Cite as

29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Proceedings{hsu_et_al:LIPIcs.ISAAC.2018,
  title =	{{LIPIcs, Volume 123, ISAAC'18, Complete Volume}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018},
  URN =		{urn:nbn:de:0030-drops-101600},
  doi =		{10.4230/LIPIcs.ISAAC.2018},
  annote =	{Keywords: Mathematics of computing, Theory of computation, Data structures design and analysis, Computing methodologies}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ISAAC.2018.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Wen-Lian Hsu, Der-Tsai Lee, and Chung-Shou Liao

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hsu_et_al:LIPIcs.ISAAC.2018.0,
  author =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{0:i--0:xviii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.0},
  URN =		{urn:nbn:de:0030-drops-99488},
  doi =		{10.4230/LIPIcs.ISAAC.2018.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ISAAC.2018.1
Going Beyond Traditional Characterizations in the Age of Big Data and Network Sciences (Invited Talk)

Authors: Shang-Hua Teng

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
What are efficient algorithms? What are network models? Big Data and Network Sciences have fundamentally challenged the traditional polynomial-time characterization of efficiency and the conventional graph-theoretical characterization of networks. More than ever before, it is not just desirable, but essential, that efficient algorithms should be scalable. In other words, their complexity should be nearly linear or sub-linear with respect to the problem size. Thus, scalability, not just polynomial-time computability, should be elevated as the central complexity notion for characterizing efficient computation. For a long time, graphs have been widely used for defining the structure of social and information networks. However, real-world network data and phenomena are much richer and more complex than what can be captured by nodes and edges. Network data are multifaceted, and thus network science requires a new theory, going beyond traditional graph theory, to capture the multifaceted data. In this talk, I discuss some aspects of these challenges. Using basic tasks in network analysis, social influence modeling, and machine learning as examples, I highlight the role of scalable algorithms and axiomatization in shaping our understanding of "effective solution concepts" in data and network sciences, which need to be both mathematically meaningful and algorithmically efficient.
Cite as

Shang-Hua Teng. Going Beyond Traditional Characterizations in the Age of Big Data and Network Sciences (Invited Talk). In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{teng:LIPIcs.ISAAC.2018.1,
  author =	{Teng, Shang-Hua},
  title =	{{Going Beyond Traditional Characterizations in the Age of Big Data and Network Sciences}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.1},
  URN =		{urn:nbn:de:0030-drops-99495},
  doi =		{10.4230/LIPIcs.ISAAC.2018.1},
  annote =	{Keywords: scalable algorithms, axiomatization, graph sparsification, local algorithms, advanced sampling, big data, network sciences, machine learning, social influence, beyond graph theory}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ISAAC.2018.2
Approximate Matchings in Massive Graphs via Local Structure (Invited Talk)

Authors: Clifford Stein

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Finding a maximum matching is a fundamental algorithmic problem and is fairly well understood in traditional sequential computing models. Some modern applications require that we handle massive graphs and hence we need to consider algorithms in models that do not allow the entire input graph to be held in the memory of one computer, or models in which the graph is evolving over time. We introduce a new concept called an "Edge Degree Constrained Subgraph (EDCS)", which is a subgraph that is guaranteed to contain a large matching, and which can be identified via local conditions. We then show how to use an EDCS to find 1.5-approximate matchings in several different models including Map Reduce, streaming and distributed computing. We can also use an EDCS to maintain a 1.5-optimal matching in a dynamic graph. This work is joint with Sepehr Asadi, Aaron Bernstein, Mohammad Hossein Bateni and Vahab Marrokni.
Cite as

Clifford Stein. Approximate Matchings in Massive Graphs via Local Structure (Invited Talk). In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{stein:LIPIcs.ISAAC.2018.2,
  author =	{Stein, Clifford},
  title =	{{Approximate Matchings in Massive Graphs via Local Structure}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.2},
  URN =		{urn:nbn:de:0030-drops-99505},
  doi =		{10.4230/LIPIcs.ISAAC.2018.2},
  annote =	{Keywords: matching, dynamic algorithms, parallel algorithms, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.3
Exploiting Sparsity for Bipartite Hamiltonicity

Authors: Andreas Björklund

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
We present a Monte Carlo algorithm that detects the presence of a Hamiltonian cycle in an n-vertex undirected bipartite graph of average degree delta >= 3 almost surely and with no false positives, in (2-2^{1-delta})^{n/2}poly(n) time using only polynomial space. With the exception of cubic graphs, this is faster than the best previously known algorithms. Our method is a combination of a variant of Björklund's 2^{n/2}poly(n) time Monte Carlo algorithm for Hamiltonicity detection in bipartite graphs, SICOMP 2014, and a simple fast solution listing algorithm for very sparse CNF-SAT formulas.
Cite as

Andreas Björklund. Exploiting Sparsity for Bipartite Hamiltonicity. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 3:1-3:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bjorklund:LIPIcs.ISAAC.2018.3,
  author =	{Bj\"{o}rklund, Andreas},
  title =	{{Exploiting Sparsity for Bipartite Hamiltonicity}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{3:1--3:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.3},
  URN =		{urn:nbn:de:0030-drops-99510},
  doi =		{10.4230/LIPIcs.ISAAC.2018.3},
  annote =	{Keywords: Hamiltonian cycle, bipartite graph}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.4
Opinion Forming in Erdös-Rényi Random Graph and Expanders

Authors: Ahad N. Zehmakan

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Assume for a graph G=(V,E) and an initial configuration, where each node is blue or red, in each discrete-time round all nodes simultaneously update their color to the most frequent color in their neighborhood and a node keeps its color in case of a tie. We study the behavior of this basic process, which is called majority model, on the Erdös-Rényi random graph G_{n,p} and regular expanders. First we consider the behavior of the majority model on G_{n,p} with an initial random configuration, where each node is blue independently with probability p_b and red otherwise. It is shown that in this setting the process goes through a phase transition at the connectivity threshold, namely (log n)/n. Furthermore, we say a graph G is lambda-expander if the second-largest absolute eigenvalue of its adjacency matrix is lambda. We prove that for a Delta-regular lambda-expander graph if lambda/Delta is sufficiently small, then the majority model by starting from (1/2-delta)n blue nodes (for an arbitrarily small constant delta>0) results in fully red configuration in sub-logarithmically many rounds. Roughly speaking, this means the majority model is an "efficient" and "fast" density classifier on regular expanders. As a by-product of our results, we show regular Ramanujan graphs are asymptotically optimally immune, that is for an n-node Delta-regular Ramanujan graph if the initial number of blue nodes is s <= beta n, the number of blue nodes in the next round is at most cs/Delta for some constants c,beta>0. This settles an open problem by Peleg [Peleg, 2014].
Cite as

Ahad N. Zehmakan. Opinion Forming in Erdös-Rényi Random Graph and Expanders. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 4:1-4:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{n.zehmakan:LIPIcs.ISAAC.2018.4,
  author =	{N. Zehmakan, Ahad},
  title =	{{Opinion Forming in Erd\"{o}s-R\'{e}nyi Random Graph and Expanders}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{4:1--4:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.4},
  URN =		{urn:nbn:de:0030-drops-99529},
  doi =		{10.4230/LIPIcs.ISAAC.2018.4},
  annote =	{Keywords: majority model, random graph, expander graphs, dynamic monopoly, bootstrap percolation}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.5
Colouring (P_r+P_s)-Free Graphs

Authors: Tereza Klimosová, Josef Malík, Tomás Masarík, Jana Novotná, Daniël Paulusma, and Veronika Slívová

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
The k-Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for a fixed integer k such that no two adjacent vertices are coloured alike. If each vertex u must be assigned a colour from a prescribed list L(u) subseteq {1,...,k}, then we obtain the List k-Colouring problem. A graph G is H-free if G does not contain H as an induced subgraph. We continue an extensive study into the complexity of these two problems for H-free graphs. We prove that List 3-Colouring is polynomial-time solvable for (P_2+P_5)-free graphs and for (P_3+P_4)-free graphs. Combining our results with known results yields complete complexity classifications of 3-Colouring and List 3-Colouring on H-free graphs for all graphs H up to seven vertices. We also prove that 5-Colouring is NP-complete for (P_3+P_5)-free graphs.
Cite as

Tereza Klimosová, Josef Malík, Tomás Masarík, Jana Novotná, Daniël Paulusma, and Veronika Slívová. Colouring (P_r+P_s)-Free Graphs. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{klimosova_et_al:LIPIcs.ISAAC.2018.5,
  author =	{Klimosov\'{a}, Tereza and Mal{\'\i}k, Josef and Masar{\'\i}k, Tom\'{a}s and Novotn\'{a}, Jana and Paulusma, Dani\"{e}l and Sl{\'\i}vov\'{a}, Veronika},
  title =	{{Colouring (P\underliner+P\underlines)-Free Graphs}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{5:1--5:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.5},
  URN =		{urn:nbn:de:0030-drops-99533},
  doi =		{10.4230/LIPIcs.ISAAC.2018.5},
  annote =	{Keywords: vertex colouring, H-free graph, linear forest}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.6
The Use of a Pruned Modular Decomposition for Maximum Matching Algorithms on Some Graph Classes

Authors: Guillaume Ducoffe and Alexandru Popa

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
We address the following general question: given a graph class C on which we can solve Maximum Matching in (quasi) linear time, does the same hold true for the class of graphs that can be modularly decomposed into C? As a way to answer this question for distance-hereditary graphs and some other superclasses of cographs, we study the combined effect of modular decomposition with a pruning process over the quotient subgraphs. We remove sequentially from all such subgraphs their so-called one-vertex extensions (i.e., pendant, anti-pendant, twin, universal and isolated vertices). Doing so, we obtain a "pruned modular decomposition", that can be computed in quasi linear time. Our main result is that if all the pruned quotient subgraphs have bounded order then a maximum matching can be computed in linear time. The latter result strictly extends a recent framework in (Coudert et al., SODA'18). Our work is the first to explain why the existence of some nice ordering over the modules of a graph, instead of just over its vertices, can help to speed up the computation of maximum matchings on some graph classes.
Cite as

Guillaume Ducoffe and Alexandru Popa. The Use of a Pruned Modular Decomposition for Maximum Matching Algorithms on Some Graph Classes. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ducoffe_et_al:LIPIcs.ISAAC.2018.6,
  author =	{Ducoffe, Guillaume and Popa, Alexandru},
  title =	{{The Use of a Pruned Modular Decomposition for Maximum Matching Algorithms on Some Graph Classes}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{6:1--6:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.6},
  URN =		{urn:nbn:de:0030-drops-99549},
  doi =		{10.4230/LIPIcs.ISAAC.2018.6},
  annote =	{Keywords: maximum matching, FPT in P, modular decomposition, pruned graphs, one-vertex extensions, P\underline4-structure}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.7
A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners

Authors: Davide Bilò and Kleitos Papadopoulos

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Given a 2-edge connected, unweighted, and undirected graph G with n vertices and m edges, a sigma-tree spanner is a spanning tree T of G in which the ratio between the distance in T of any pair of vertices and the corresponding distance in G is upper bounded by sigma. The minimum value of sigma for which T is a sigma-tree spanner of G is also called the stretch factor of T. We address the fault-tolerant scenario in which each edge e of a given tree spanner may temporarily fail and has to be replaced by a best swap edge, i.e. an edge that reconnects T-e at a minimum stretch factor. More precisely, we design an O(n^2) time and space algorithm that computes a best swap edge of every tree edge. Previously, an O(n^2 log^4 n) time and O(n^2+m log^2n) space algorithm was known for edge-weighted graphs [Bilò et al., ISAAC 2017]. Even if our improvements on both the time and space complexities are of a polylogarithmic factor, we stress the fact that the design of a o(n^2) time and space algorithm would be considered a breakthrough.
Cite as

Davide Bilò and Kleitos Papadopoulos. A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 7:1-7:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.ISAAC.2018.7,
  author =	{Bil\`{o}, Davide and Papadopoulos, Kleitos},
  title =	{{A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{7:1--7:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.7},
  URN =		{urn:nbn:de:0030-drops-99557},
  doi =		{10.4230/LIPIcs.ISAAC.2018.7},
  annote =	{Keywords: Transient edge failure, best swap edges, tree spanner}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.8
Efficient Enumeration of Dominating Sets for Sparse Graphs

Authors: Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura, and Takeaki Uno

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
A dominating set D of a graph G is a set of vertices such that any vertex in G is in D or its neighbor is in D. Enumeration of minimal dominating sets in a graph is one of central problems in enumeration study since enumeration of minimal dominating sets corresponds to enumeration of minimal hypergraph transversal. However, enumeration of dominating sets including non-minimal ones has not been received much attention. In this paper, we address enumeration problems for dominating sets from sparse graphs which are degenerate graphs and graphs with large girth, and we propose two algorithms for solving the problems. The first algorithm enumerates all the dominating sets for a k-degenerate graph in O(k) time per solution using O(n + m) space, where n and m are respectively the number of vertices and edges in an input graph. That is, the algorithm is optimal for graphs with constant degeneracy such as trees, planar graphs, H-minor free graphs with some fixed H. The second algorithm enumerates all the dominating sets in constant time per solution for input graphs with girth at least nine.
Cite as

Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura, and Takeaki Uno. Efficient Enumeration of Dominating Sets for Sparse Graphs. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kurita_et_al:LIPIcs.ISAAC.2018.8,
  author =	{Kurita, Kazuhiro and Wasa, Kunihiro and Arimura, Hiroki and Uno, Takeaki},
  title =	{{Efficient Enumeration of Dominating Sets for Sparse Graphs}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{8:1--8:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.8},
  URN =		{urn:nbn:de:0030-drops-99560},
  doi =		{10.4230/LIPIcs.ISAAC.2018.8},
  annote =	{Keywords: Enumeration algorithm, polynomial amortized time, dominating set, girth, degeneracy}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.9
Complexity of Unordered CNF Games

Authors: Md Lutfar Rahman and Thomas Watson

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
The classic TQBF problem is to determine who has a winning strategy in a game played on a given CNF formula, where the two players alternate turns picking truth values for the variables in a given order, and the winner is determined by whether the CNF gets satisfied. We study variants of this game in which the variables may be played in any order, and each turn consists of picking a remaining variable and a truth value for it. - For the version where the set of variables is partitioned into two halves and each player may only pick variables from his/her half, we prove that the problem is PSPACE-complete for 5-CNFs and in P for 2-CNFs. Previously, it was known to be PSPACE-complete for unbounded-width CNFs (Schaefer, STOC 1976). - For the general unordered version (where each variable can be picked by either player), we also prove that the problem is PSPACE-complete for 5-CNFs and in P for 2-CNFs. Previously, it was known to be PSPACE-complete for 6-CNFs (Ahlroth and Orponen, MFCS 2012) and PSPACE-complete for positive 11-CNFs (Schaefer, STOC 1976).
Cite as

Md Lutfar Rahman and Thomas Watson. Complexity of Unordered CNF Games. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{rahman_et_al:LIPIcs.ISAAC.2018.9,
  author =	{Rahman, Md Lutfar and Watson, Thomas},
  title =	{{Complexity of Unordered CNF Games}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{9:1--9:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.9},
  URN =		{urn:nbn:de:0030-drops-99574},
  doi =		{10.4230/LIPIcs.ISAAC.2018.9},
  annote =	{Keywords: CNF, Games, PSPACE-complete, SAT, Linear Time}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.10
Half-Duplex Communication Complexity

Authors: Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, and Alexander V. Smal

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Suppose Alice and Bob are communicating in order to compute some function f, but instead of a classical communication channel they have a pair of walkie-talkie devices. They can use some classical communication protocol for f where in each round one player sends a bit and the other one receives it. The question is whether talking via walkie-talkie gives them more power? Using walkie-talkies instead of a classical communication channel allows players two extra possibilities: to speak simultaneously (but in this case they do not hear each other) and to listen at the same time (but in this case they do not transfer any bits). The motivation for this kind of a communication model comes from the study of the KRW conjecture. We show that for some definitions this non-classical communication model is, in fact, more powerful than the classical one as it allows to compute some functions in a smaller number of rounds. We also prove lower bounds for these models using both combinatorial and information theoretic methods.
Cite as

Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, and Alexander V. Smal. Half-Duplex Communication Complexity. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 10:1-10:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hoover_et_al:LIPIcs.ISAAC.2018.10,
  author =	{Hoover, Kenneth and Impagliazzo, Russell and Mihajlin, Ivan and Smal, Alexander V.},
  title =	{{Half-Duplex Communication Complexity}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{10:1--10:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.10},
  URN =		{urn:nbn:de:0030-drops-99583},
  doi =		{10.4230/LIPIcs.ISAAC.2018.10},
  annote =	{Keywords: communication complexity, half-duplex channel, information theory}
}
  • Refine by Author
  • 3 Björklund, Andreas
  • 2 Bilò, Davide
  • 2 Cuyt, Annie
  • 2 Ducoffe, Guillaume
  • 2 Erlebach, Thomas
  • Show More...

  • Refine by Classification
  • 12 Theory of computation → Design and analysis of algorithms
  • 9 Mathematics of computing → Graph theory
  • 9 Theory of computation → Computational geometry
  • 8 Mathematics of computing → Graph algorithms
  • 8 Theory of computation → Graph algorithms analysis
  • Show More...

  • Refine by Keyword
  • 3 FPT in P
  • 2 Approximation Algorithms
  • 2 Approximation algorithms
  • 2 Maximal Adjacency Ordering
  • 2 Maximum Cardinality Search
  • Show More...

  • Refine by Type
  • 79 document
  • 1 volume

  • Refine by Publication Year
  • 75 2018
  • 2 2022
  • 1 2006
  • 1 2016
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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