| 1. |
- Björklund, Andreas, et al.
(författare)
-
Spotting Trees with Few Leaves
- 2015
-
Ingår i: Lecture Notes in Computer Science/Automata, Languages, and Programming. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 0302-9743 .- 1611-3349. - 9783662476727 ; 9134, s. 243-255
-
Konferensbidrag (refereegranskat)abstract
- We show two results related to the Hamiltonicity and k -Path algorithms in undirected graphs by Björklund [FOCS’10], and Björklund et al., [arXiv’10]. First, we demonstrate that the technique used can be generalized to finding some k-vertex tree with l leaves in an n-vertex undirected graph in O∗(1.657^k2^{l/2}) time. It can be applied as a subroutine to solve the k -Internal Spanning Tree (k-IST) problem in O∗(min(3.455^k,1.946^n)) time using polynomial space, improving upon previous algorithms for this problem. In particular, for the first time, we break the natural barrier of O∗(2^n). Second, we show that the iterated random bipartition employed by the algorithm can be improved whenever the host graph admits a vertex coloring with few colors; it can be an ordinary proper vertex coloring, a fractional vertex coloring, or a vector coloring. In effect, we show improved bounds for k-Path and Hamiltonicity in any graph of maximum degree Δ=4,…,12 or with vector chromatic number at most 8.
|
|
| 2. |
|
|
| 3. |
- Haghighatkhah, Pantea, et al.
(författare)
-
Characterizing Uncertainty in the Visual Text Analysis Pipeline
- 2022
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- Current visual text analysis approaches rely on sophisticated processing pipelines. Each step of such a pipeline potentially amplifies any uncertainties from the previous step. To ensure the comprehensibil- ity and interoperability of the results, it is of paramount importance to clearly communicate the uncertainty not only of the output but also within the pipeline. In this paper, we characterize the sources of uncertainty along the visual text analysis pipeline. Within its three phases of labeling, modeling, and analysis, we identify six sources, discuss the type of uncertainty they create, and how they propagate. The goal of this paper is to bring the attention of the visualization community to additional types and sources of uncer- tainty in visual text analysis and to call for careful consideration, highlighting opportunities for future research.
|
|
| 4. |
- Haghighatkhah, Pantea, et al.
(författare)
-
Characterizing Uncertainty in the Visual Text Analysis Pipeline
- 2022
-
Ingår i: Proceedings - 2022 IEEE 7th Workshop on Visualization for the Digital Humanities, VIS4DH 2022. - 9781665476683 ; , s. 25-30
-
Konferensbidrag (refereegranskat)abstract
- Current visual text analysis approaches rely on sophisticated processing pipelines. Each step of such a pipeline potentially amplifies any uncertainties from the previous step. To ensure the comprehensibility and interoperability of the results, it is of paramount importance to clearly communicate the uncertainty not only of the output but also within the pipeline. In this paper, we characterize the sources of uncertainty along the visual text analysis pipeline. Within its three phases of labeling, modeling, and analysis, we identify six sources, discuss the type of uncertainty they create, and how they propagate. The goal of this paper is to bring the attention of the visualization community to additional types and sources of uncertainty in visual text analysis and to call for careful consideration, highlighting opportunities for future research.
|
|
| 5. |
- Hammarström, Harald, et al.
(författare)
-
Simultaneous Visualization of Language Endangerment and Language Description
- 2018
-
Ingår i: Language Documentation & Conservation. - : University of Hawai'i Press. - 1934-5275. ; 12, s. 359-392
-
Tidskriftsartikel (refereegranskat)abstract
- The world harbors a diversity of some 6,500 mutually unintelligible languages. As has been increasingly observed by linguists, many minority languages are becoming endangered and will be lost forever if not documented. Urgently indeed, many efforts are being launched to document and describe languages. This undertaking naturally has the priority toward the most endangered and least described languages. For the first time, we combine world-wide databases on language description (Glottolog) and language endangerment (ElCat, Ethnologue, UNESCO) and provide two online interfaces, GlottoScope and GlottoVis, to visualize these together. The interfaces are capable of browsing, filtering, zooming, basic statistics, and different ways of combining the two measures on a world map background. GlottoVis provides advanced techniques for combining cluttered dots on a map. With the tools and databases described we seek to increase the overall knowledge of the actual state language endangerment and description worldwide.
|
|
| 6. |
- Hershberger, John, et al.
(författare)
-
Geometric kth shortest paths : The applet
- 2014
-
Ingår i: Proceedings of the thirtieth annual symposium on Computational geometry.
-
Konferensbidrag (refereegranskat)abstract
- Computing shortest paths in a polygonal do- main is a classic problem in computational geometry. Ecient algorithms for computing such paths use the continuous Dijk- stra paradigm [2], which not only allows one to nd the short- est path between two points but also computes the \shortest path map" from a given source|a structure enabling ecient queries of shortest paths to points in the domain.
|
|
