Outputs (3144)

Finding Paths in Graphs Avoiding Forbidden Transitions; (2003)
Journal Article
Szeider, S. (2003). Finding Paths in Graphs Avoiding Forbidden Transitions;. Discrete Applied Mathematics, 126(2-3), 261-273. https://doi.org/10.1016/s0166-218x%2802%2900251-2

Let v be a vertex of a graph G; a transition graph T(v) of v is a graph whose vertices are the edges incident with v. We consider graphs G with prescribed transition systems T={T(v) | vV(G)}. A path P in G is called T-compatible, if each pair uv,vw o... Read More about Finding Paths in Graphs Avoiding Forbidden Transitions;.

Using program schemes to capture polynomial-time logically on certain classes of structures (2003)
Journal Article
Stewart, I. (2003). Using program schemes to capture polynomial-time logically on certain classes of structures. LMS journal of computation and mathematics, 6, 40-67

We continue the study of the expressive power of certain classes of program schemes on finite structures, in relation to more mainstream logics studied in finite model theory and to computational complexity. We show that there exists a program scheme... Read More about Using program schemes to capture polynomial-time logically on certain classes of structures.

The natural work-stealing algorithm is stable (2003)
Journal Article
Berenbrink, P., Friedetzky, T., & Goldberg, L. (2003). The natural work-stealing algorithm is stable. SIAM Journal on Computing, 32(5), 1260-1279. https://doi.org/10.1137/s0097539701399551

In this paper we analyze a very simple dynamic work-stealing algorithm. In the work-generation model, there are n (work) generators. A generator-allocation function is simply a function from the n generators to the n processors. We consider a fixed,... Read More about The natural work-stealing algorithm is stable.

Greedy algorithms, H-colourings and a complexity-theoretic dichotomy (2003)
Journal Article
Puricella, A., & Stewart, I. (2003). Greedy algorithms, H-colourings and a complexity-theoretic dichotomy. Theoretical Computer Science, 290(3), 1897-1913. https://doi.org/10.1016/s0304-3975%2802%2900329-8

Let H be a fixed undirected graph. An H-colouring of an undirected graph G is a homomorphism from G to H. If the vertices of G are partially ordered then there is a generic non-deterministic greedy algorithm which computes all lexicographically first... Read More about Greedy algorithms, H-colourings and a complexity-theoretic dichotomy.

Solving order constraints in logarithmic space (2003)
Presentation / Conference Contribution
Krokhin, A., & Larose, B. (2003, January). Solving order constraints in logarithmic space. Presented at Proceedings of the 20th International Symposium on Theoretical Aspects of Computer Science {(STACS'03) Berlin, Berlin

We combine methods of order theory, finite model theory, and universal algebra to study, within the constraint satisfaction framework, the complexity of some well-known combinatorial problems connected with a finite poset. We identify some conditions... Read More about Solving order constraints in logarithmic space.

Identifying Cause and Effect Relations between Events in Concurrent Event-Based Components (2003)
Presentation / Conference Contribution
Dias, M., & Richardson, D. J. (2002, September). Identifying Cause and Effect Relations between Events in Concurrent Event-Based Components. Presented at 17th IEE International Conference on Automated Software Engineering, Edinburgh, UK

Concurrent event-based components present characteristics that impose difficulties in understanding their dynamic behavior, mainly for interpreting the cause and effect relations between input and output events in component interactions. In this pape... Read More about Identifying Cause and Effect Relations between Events in Concurrent Event-Based Components.

Orientation and solvatochromism of dyes in liquid crystals (2003)
Journal Article
Palsson, L., Szablewski, M., Roberts, A., Masutani, A., Love, G., Cross, G., …Yasuda, A. (2003). Orientation and solvatochromism of dyes in liquid crystals. Molecular Crystals and Liquid Crystals, 402(1), 43-53. https://doi.org/10.1080/744816685

The orientation and solvatochromism of some dye molecules in a liquid crystal have been investigated. Interactions with the host and the structure of the dye molecule affect the macroscopic alignment of dichroic dye molecules in a liquid crystal: It... Read More about Orientation and solvatochromism of dyes in liquid crystals.

A note on first-order projections and games (2003)
Journal Article
Arratia, A., & Stewart, I. (2003). A note on first-order projections and games. Theoretical Computer Science, 290(3), 2085-2093. https://doi.org/10.1016/s0304-3975%2802%2900491-7

We show how the fact that there is a first-order projection from the problem TC (transitive closure) to some other problem $\Omega$ enables us to automatically deduce that a natural game problem, $\mathcal{LG}(\Omega)$, whose instances are labelled i... Read More about A note on first-order projections and games.

A novel multipath dispersion reduction technique based on controlled-polarization optical wireless link set-up (2003)
Presentation / Conference Contribution
Giakos, G., Patnekar, N., Sumrain, S., Fraiwan, L., Kumar, V., & Mertzios, G. (2003, December). A novel multipath dispersion reduction technique based on controlled-polarization optical wireless link set-up. Presented at IEEE Instrumentation and Measurement Technology Conference (IMTC 2003), Vail, Co

The detection characteristics of an indoor-optical communication system, which utilizes infrared radiation as carrier has been explored and enhanced for telemedicine, and wireless local area network applications. The novelty of the presented techniqu... Read More about A novel multipath dispersion reduction technique based on controlled-polarization optical wireless link set-up.

Norm Gibbs and his contribution to software engineering education through the SEI curriculum modules (2003)
Presentation / Conference Contribution
Budgen, D., & Tomayko, J. E. (2002, February). Norm Gibbs and his contribution to software engineering education through the SEI curriculum modules. Presented at Software Engineering Education Conference, Proceedings, Madrid, Spain

The Software Engineering Institute (SEI) at Carnegie Mellon University started its first contract with a carte blanche opportunity and generous funding to improve the state of software engineering education. Norm Gibbs, the first Director of Educatio... Read More about Norm Gibbs and his contribution to software engineering education through the SEI curriculum modules.