Change search
Refine search result
1 - 14 of 14
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1. Alimonti, P.
    et al.
    Kann, Viggo
    KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.
    Some APX-completeness results for cubic graphs2000In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 237, no 2-Jan, p. 123-134Article in journal (Refereed)
    Abstract [en]

    Four fundamental graph problems, Minimum vertex cover, Maximum independent set, Minimum dominating set and Maximum cut, are shown to be APX-complete even for cubic graphs. Therefore, unless P = NP, these problems do not admit any polynomial time approximation scheme on input graphs of degree bounded by three.

  • 2. Bar-Noy, Amotz
    et al.
    Cheilaris, Panagiotis
    Lampis, Michael
    Mitsou, Valia
    Zachos, Stathis
    Ordered Coloring for Grids and Related Graphs2011In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294Article in journal (Refereed)
    Abstract [en]

     We investigate a coloring problem, called ordered coloring, in grids and some other families of grid-like graphs. Ordered coloring (also known as vertex ranking) is related to conflict-free coloring and other traditional coloring problems. Such coloring problems can model (among others) efficient frequency assignments in cellular networks. Our main technical results improve upper and lower bounds for the ordered chromatic number of grids and related graphs. To the best of our knowledge, this is the first attempt to calculate exactly the ordered chromatic number of these graph families.

  • 3. Bar-Noy, Amotz
    et al.
    Cheilaris, Panagiotis
    Lampis, Michael
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Mitsou, Valia
    Zachos, Stathis
    Ordered coloring of grids and related graphs2012In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 444, p. 40-51Article in journal (Refereed)
    Abstract [en]

    We investigate a coloring problem, called ordered coloring, in grids and some other families of grid-like graphs. Ordered coloring (also known as vertex ranking) has applications, among other areas, in efficient solving of sparse linear systems of equations and scheduling parallel assembly of products. Our main technical results improve upper and lower bounds for the ordered chromatic number of grids and related graphs.

  • 4.
    Björner, Anders
    et al.
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Sagan, Bruce E.
    Rationality of the Mobius function of a composition poset2006In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 359, no 3-Jan, p. 282-298Article in journal (Refereed)
    Abstract [en]

    We consider the zeta and Mobius functions of a partial order on integer compositions first studied by Bergeron, Bousquet-Melou, and Dulucq. The Mobius function of this poset was determined by Sagan and Vatter. We prove rationality of various formal power series in noncommuting variables whose coefficients are evaluations of the zeta function, zeta, and the Mobius function, mu. The proofs are either directly from the definitions or by constructing finite-state automata. We also obtain explicit expressions for generating functions obtained by specializing the variables to commutative ones. We reprove Sagan and Vatter's formula for it using this machinery. These results are closely related to those of Bjorner and Reutenauer about subword order, and we discuss a common generalization.

  • 5. Bryant, D.
    et al.
    Lagergren, Jens
    KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.
    Compatibility of unrooted phylogenetic trees is FPT2006In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 351, no 3, p. 296-302Article in journal (Refereed)
    Abstract [en]

    A collection of T-1, T-2,..., T-k of unrooted, leaf labelled (phylogenetic) trees, all with different leaf sets, is said to be compatible if there exists a tree T such that each tree T-i can be obtained from T by deleting leaves and contracting edges. Determining compatibility is NP-hard, and the fastest algorithm to date has worst case complexity of around Omega(n(k)) time, n being the number of leaves. Here, we present an O(nf (k)) algorithm, proving that compatibility of unrooted phylogenetic trees is fixed parameter tractable (FPT) with respect to the number k of trees.

  • 6.
    Böckenhauer, Hans-Joachim
    et al.
    ETH Zurich.
    Hromkovič, Juraj
    ETH Zurich.
    Královič, Richard
    ETH Zurich.
    Mömke, Tobias
    ETH Zurich.
    Rossmanith, Peter
    RWTH Aachen.
    Reoptimization of Steiner Trees: Changing the Terminal Set2009In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 410, no 36, p. 3428-3435Article in journal (Refereed)
    Abstract [en]

    Given an instance of the Steiner tree problem together with an optimalsolution, we consider the scenario where this instance is modifiedlocally by adding one of the vertices to the terminal set or removing onevertex from it. In this paper, we investigate the problem whether theknowledge of an optimal solution to the unaltered instance can help insolving the locally modified instance. Our results are as follows:

    - We prove that these reoptimization variants of the Steiner treeproblem are NP-hard, even if edge costs are restricted to values from {1,2}.

    - We design 1.5-approximation algorithms for both variants of localmodifications. This is an improvement over the currently best knownapproximation algorithm for the classical Steiner tree problem whichachieves an approximation ratio of 1+ln(3)/2 \approx 1.55.

    - We present a PTAS for the subproblem in which the edge costs arenatural numbers {1,...,k} for some constant k.

  • 7.
    Chiesa, Marco
    et al.
    Université catholique du Louvain, Belgium.
    Di Battista, G.
    Erlebach, T.
    Patrignani, M.
    Computational complexity of traffic hijacking under BGP and S-BGP2015In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 600, p. 143-154Article in journal (Refereed)
    Abstract [en]

    Harmful Internet hijacking incidents put in evidence how fragile interdomain routing is. In particular, the Border Gateway Protocol (BGP), which is used to exchange routing information between Internet entities, called Autonomous Systems (ASes), proved to be prone to attacks launched by a single malicious AS. Recent research contributions pointed out that even S-BGP, the secure variant of BGP that is being deployed, is not fully able to blunt traffic attraction attacks. Given a traffic flow between two ASes, we study how difficult it is for a malicious AS to devise a strategy for hijacking or intercepting that flow. The goal of the attack is to attract a traffic flow towards the malicious AS. While in the hijacking attack connectivity between the endpoints of a flow can be disrupted, in the interception attack connectivity must be maintained. We show that this problem marks a sharp difference between BGP and S-BGP. Namely, while it is solvable, under reasonable assumptions, in polynomial time for the type of attacks that are usually performed in BGP, it is NP-hard for S-BGP. Our study has several by-products. E.g., we solve a problem left open in the literature, stating when performing a hijacking in S-BGP is equivalent to performing an interception.

  • 8.
    Elias, Isaac
    et al.
    KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.
    Lagergren, Jens
    KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.
    Fast Neighbor Joining2009In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 410, no 21-23, p. 1993-2000Article in journal (Refereed)
    Abstract [en]

     Reconstructing the evolutionary history of a set of species is a fundamental problem in biology and methods for solving this problem are gaged based on two characteristics: accuracy and efficiency. Neighbor joining (NJ) is a so-called distance-based method that, thanks to its good accuracy and speed, has been embraced by the phylogeny community. it takes the distances between n taxa and produces in Theta(n(3)) time a phylogenetic tree, i.e., a tree which aims to describe the evolutionary history of the taxa. In addition to performing well in practice, the NJ algorithm has optimal reconstruction radius.

    The contribution of this paper is twofold: (1) we present an algorithm called Fast Neighbor Joining(FNJ) with optimal reconstruction radius and optimal run time complexity O(n(2)) and (2) we present a greatly simplified proof for the correctness of NJ. initial experiments show that FNJ in practice has almost the same accuracy as NJ, indicating that the property of optimal reconstruction radius has great importance to their good performance. Moreover, we show how improved running time can be achieved for Computing the so-called correction formulas.

  • 9.
    Engebretsen, Lars
    et al.
    KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.
    Holmerin, Jonas
    KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.
    Russell, A.
    Inapproximability results for equations over finite groups2004In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 312, no 1, p. 17-45Article in journal (Refereed)
    Abstract [en]

    An equation over a finite group G is an expression of form w(1)w(2). . .w(k) = 1(G), where each w(i) is a variable, an inverted variable, or a constant from G; such an equation is satisfiable if there is a setting of the variables to values in G so that the equality is realized. We study the problem of simultaneously satisfying a family of equations over a finite group G and show that it is NP-hard to approximate the number of simultaneously satisfiable equations to within \G\ - epsilon for any epsilon > 0. This generalizes results of Hastad (J. ACM 48 (4) (2001) 798), who established similar bounds under the added condition that the group G is Abelian.

  • 10.
    Fersman, Elena
    et al.
    Ericsson Research, Ericsson AB.
    Mokrushin, Leonid
    Pettersson, Paul
    Yi, Wang
    Schedulability Analysis of Fixed-Priority Systems using Timed Automata2006In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 354, no 2, p. 301-317Article in journal (Refereed)
    Abstract [en]

    In classic scheduling theory, real-time tasks are usually assumed to be periodic, i.e. tasks are released and computed with fixed rates periodically. To relax the stringent constraints on task arrival times, we propose to use timed automata to describe task arrival patterns. In a previous work, it is shown that the general schedulability checking problem for such models is a reachability problem for a decidable class of timed automata extended with subtraction. Unfortunately, the number of clocks needed in the analysis is proportional to the maximal number of schedulable task instances associated with a model, which is in many cases huge. In this paper, we show that for fixed-priority scheduling strategy, the schedulability checking problem can be solved using standard timed automata with two   extra clocks in addition to the clocks used in the original model to describe task arrival times. The analysis can be done in a similar manner to response time analysis in classic Rate-Monotonic Analysis (RMA). The result is further extended to systems with data-dependent control, in which the release time of a task may depend on the time-point at which other tasks finish their execution. For the case when the execution times of tasks are constants, we show that the schedulability problem can be solved using n+1n+1 extra clocks, where nn is the number of tasks. The presented analysis techniques have been implemented in the Times tool. For systems with only periodic tasks, the performance of the tool is comparable with tools implementing the classic RMA technique based on equation-solving, without suffering from the exponential explosion in the number of tasks.

  • 11. Fried, D.
    et al.
    Shimony, S. E.
    Benbassat, A.
    Wenner, Cenny
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Complexity of Canadian traveler problem variants2013In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 487, p. 1-16Article in journal (Refereed)
    Abstract [en]

    The Canadian traveler problem (CTP) is the problem of traversing a given graph, where some of the edges may be blocked-a state which is revealed only upon reaching an incident vertex. Originally stated by Papadimitriou and Yannakakis (1991) [1], the adversarial version of the CTP was shown to be PSPACE-complete, with the stochastic version shown to be in PSPACE and #P-hard. We show that the stochastic CTP is also PSPACE-complete: initially proving PSPACE-hardness for the dependent version of the stochastic CTP, and proceeding with gadgets that allow us to extend the proof to the independent case. Since for disjoint-path graphs, the CTP can be solved in polynomial time, we examine the complexity of the more general remote-sensing CTP, and show that it is NP-hard even for disjoint-path graphs.

  • 12.
    Gurov, Dilian
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Huisman, Marieke
    University of Twente, Netherlands .
    Reducing behavioural to structural properties of programs with procedures2013In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 480, p. 69-103Article in journal (Refereed)
    Abstract [en]

    There is an intimate link between program structure and behaviour. Exploiting this link to phrase program correctness problems in terms of the structural properties of a program graph rather than in terms of its unfoldings is a useful strategy for making analyses more tractable. The present paper presents a characterisation of behavioural program properties through sets of structural properties by means of a translation. The characterisation is given in the context of a program model based on control flow graphs of sequential programs with procedures, abstracting away completely from program data, and properties expressed in a fragment of the modal mu-calculus with boxes and greatest fixed-points only. The property translation is based on a tableau construction that conceptually amounts to symbolic execution of the behavioural formula, collecting structural constraints along the way. By keeping track of the subformulae that have been examined, recursion in the structural constraints can be identified and captured by fixed-point formulae. The tableau construction terminates, and the characterisation is exact, i.e., the translation is sound and complete. A prototype implementation has been developed. In addition, we show how the translation can be extended beyond the basic flow graph model and safety logic to richer behavioural models (such as open programs) and richer program models (including Boolean programs), and discuss possible extensions for more complex logics. We present several applications of the characterisation, in particular sound and complete compositional verification for behavioural properties based on maximal models.

  • 13.
    Haller, Philipp
    et al.
    EPFL, Switzerland.
    Odersky, Martin
    EPFL, Switzerland.
    Scala Actors: Unifying thread-based and event-based programming2009In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 410, no 2-3, p. 202-220Article in journal (Refereed)
    Abstract [en]

    There is an impedance mismatch between message-passing concurrency and virtual machines, such as the JVM. VMs usually map their threads to heavyweight OS processes. Without a lightweight process abstraction, users are often forced to write parts of concurrent applications in an event-driven style which obscures control flow, and increases the burden on the programmer. In this paper we show how thread-based and event-based programming can be unified under a single actor abstraction. Using advanced abstraction mechanisms of the Scala programming language, we implement our approach on unmodified JVMs. Our programming model integrates well with the threading model of the underlying VM.

  • 14.
    Hamrin, Göran
    et al.
    Matematiska institutionen, Uppsala universitet.
    Stoltenberg-Hansen, Viggo
    Matematiska institutionen, Uppsala universitet.
    Two categories of effective continuous cpos2006In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 365, no 3, p. 216-236Article in journal (Refereed)
    Abstract [en]

    This paper presents two categories of effective continuous complete partial orders (cpos). We define a new criterion on the basis of a cpo so as to make the resulting category of consistently complete continuous cpos cartesian closed. We also generalise to continuous cpos the definition of a complete set, which was used as a definition of effective bifinite domains in Hamrin and Stoltenberg-Hansen [Cartesian closed categories of effective domains, in: H. Schwichtenberg, R. Steinbruggen (Eds.), Proof and System-Reliability, Kluwer Academic Publishers, Dordrecht, 2002, pp. 1-20], and investigate the closure results that can be obtained.

1 - 14 of 14
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf