Information Processing Letters

Journal: Information Processing Letters

Abbreviation

Inf. process. lett.

Publisher

Elsevier

ISSN

0020-0190
1872-6119

Show all metadata

Search Results

Publications 1 - 10 of 19

Deciding safety and liveness in TPTL
Basin, David; Cotrini Jimenez, Carlos; Klaedtke, Felix; et al. (2014)
Information Processing Letters
Resource constrained scheduling on multiple machines
Remy, Jan (2004)
Information Processing Letters
On the spectrum of projective norm-graphs
Szabó, Tibor (2003)
Information Processing Letters
Alternating paths through disjoint line segments
Hoffmann, Michael; Tóth, Csaba D. (2003)
Information Processing Letters
Improved hardness results for unique shortest vector problem
Aggarwal, Divesh; Dubey, Chandan K. (2016)
Information Processing Letters
Time and space optimality of rotor-router graph exploration
Menc, Artur; Pająk D.; Uznański, Przemysław (2017)
Information Processing Letters
Online Graph Exploration on Trees, Unicyclic Graphs and Cactus Graphs
Fritsch, Robin (2021)
Information Processing Letters
We study the problem of exploring all vertices of an undirected weighted graph that is initially unknown to the searcher. An edge of the graph is only revealed when the searcher visits one of its endpoints. Beginning at some start node, the searcher's goal is to visit every vertex of the graph before returning to the start node on a tour as short as possible. We prove that the Nearest Neighbor algorithm's competitive ratio on trees with n vertices is Ө (log n), i.e. no better than on general graphs. Furthermore, we examine the algorithm Blocking for a range of parameters not considered previously and prove it is 3-competitive on unicyclic graphs as well as 5/2 + √s ≈ 3.91 -competitive on cactus graphs. The best known lower bound for these two graph classes is 2.
Adding cardinality constraints to integer programs with applications to maximum satisfiability
Bläser, Markus; Heynen, Thomas; Manthey, Bodo (2008)
Information Processing Letters
Shorter strings containing all k-element permutations
Zălinescu, Eugen (2011)
Information Processing Letters
Finding the detour-critical edge of a shortest path between two nodes
Nardelli, Enrico; Proietti, Guido; Widmayer, Peter (1998)
Information Processing Letters

Publications 1 - 10 of 19

Journal: Information Processing Letters

Abbreviation

Publisher

Journal Volumes

ISSN

Description

Filters

Search Results