VLDB 2026 Research / reviewers in the wild / expert
Andrzej Szepietowski
dblp:96/2354
· DBLP profile ↗
26ranked-venue papers
19as first author
1since 2021 · last 2021
0000-0002-4884-3811ORCID · verified
Domains — the database's venue-derived domains; a paper can count in several
Databases, data management, data science and information retrieval · 22 · 16 first-author · 1 since 2021Theory of computation · 19 · 13 first-author · 1 since 2021
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2021 | Hamiltonian cycles and paths in hypercubes with disjoint faulty edges
Janusz Dybizbanski, Andrzej Szepietowski |
Inf. Process. Lett. | 2 |
| 2020 | Signed coloring of 2-dimensional gridsabstractA signed graph is a pair (G,σ), where G=(V(G),E(G)) is an undirected graph and σ:E(G)→{+,−} is a function which marks each edge with “+” or “−”. Two signed graphs are equivalent if one of them can be changed to the other by a sequence of resigning operations. The single resigning operation chooses a vertex v∈V(G) and flips the signs of all edges incident to v. By [G,σ] we shall denote the equivalence class of the signed graph (G,σ). Each element of [G,σ] is called a presentation of [G,σ]. In this paper we shall call both (G,σ) and [G,σ] signed graphs. The coloring of signed graphs is defined through homomorphism. The signed graph [G,σ] is colored by the signed graph (G2,σ2), if there exists a presentation (G,σ1) of [G,σ] and a vertex-mapping ϕ from G to G2 which preserves signs of the edges. In this paper we show that: (a) The signed chromatic number for the class G of all 2-dimensional grids lies between 5 and 6. (b) Every signed grid with at most seven rows can be colored with five colors. (c) Every signed grid with two rows can be colored with four colors. Janusz Dybizbanski, Anna Nenca, Andrzej Szepietowski |
Inf. Process. Lett. | 3 |
| 2017 | Hamiltonian paths in hypercubes with local traps
Janusz Dybizbanski, Andrzej Szepietowski |
Inf. Sci. | 2 |
| 2014 | The oriented chromatic number of Halin graphs
Janusz Dybizbanski, Andrzej Szepietowski |
Inf. Process. Lett. | 2 |
| 2012 | Hamiltonian cycles in hypercubes with 2n-4 faulty edges
Andrzej Szepietowski |
Inf. Sci. | 1 |
| 2008 | Fooling Turing machines with sublogarithmic space: a note on 'For completeness, sublogarithmic space is no space' by M. Agrawal
Andrzej Szepietowski |
Inf. Process. Lett. | 1 |
| 2006 | A note on alternating one-pebble Turing machines with sublogarithmic space
Andrzej Szepietowski |
Inf. Process. Lett. | 1 |
| 2004 | A note on the oriented chromatic number of grids
Andrzej Szepietowski, Monika Targan |
Inf. Process. Lett. | 1 |
| 2002 | Complexity of weak acceptance conditions in tree automata
Jakub Neumann, Andrzej Szepietowski, Igor Walukiewicz |
Inf. Process. Lett. | 2 |
| 2001 | Algorithms counting monotone Boolean functions
Robert Fidytek, Andrzej Wlodzimierz Mostowski, Rafal Somla, Andrzej Szepietowski |
Inf. Process. Lett. | 4 |
| 2001 | Shuffle languages are in P
Joanna Jedrzejowicz, Andrzej Szepietowski |
Theor. Comput. Sci. | 2 |
| 1998 | Weak and Strong One-Way Space Complexity Classes
Andrzej Szepietowski |
Inf. Process. Lett. | 1 |
| 1996 | The Element Distinctness Problem on One-Tape Turing Machines
Andrzej Szepietowski |
Inf. Process. Lett. | 1 |
| 1992 | Two-dimensional on-line tessellation acceptors are not closed under complement
Andrzej Szepietowski |
Inf. Sci. | 1 |
| 1992 | Some remarks on two-dimensional finite automata
Andrzej Szepietowski |
Inf. Sci. | 1 |
| 1992 | On space functions constructed by two-dimensional turing machines
Andrzej Szepietowski |
Inf. Sci. | 1 |
| 1991 | On three-way two-dimensional multicounter automata
Andrzej Szepietowski |
Inf. Sci. | 1 |
| 1990 | If Deterministic and Nondeterministic Space Complexities are Equal for log log n, then they are also Equal for log n
Andrzej Szepietowski |
Theor. Comput. Sci. | 1 |
| 1989 | If Deterministic and Nondeterministic Space Complexities are Equal for log log n then they are also Equal for log n
Andrzej Szepietowski |
STACS | 1 |
| 1989 | Some Remarks on the Alternating Hierarchy and Closure Under Complement for Sublogarithmic Space
Andrzej Szepietowski |
Inf. Process. Lett. | 1 |
| 1989 | Some Notes on Strong and Weak log log n Space Complexity
Andrzej Szepietowski |
Inf. Process. Lett. | 1 |
| 1989 | On three-way two-dimensional turing machines
Andrzej Szepietowski |
Inf. Sci. | 1 |
| 1988 | Remarks on Languages Acceptable in log n Space
Andrzej Szepietowski |
Inf. Process. Lett. | 1 |
| 1987 | There are no Fully Space Constructible Functions Between log log n and log n
Andrzej Szepietowski |
Inf. Process. Lett. | 1 |
| 1983 | Remarks on Searching Labyrinths by Automata
Andrzej Szepietowski |
FCT | 1 |
| 1982 | A Finite 5-Pebble-Automaton Can Search Every Maze
Andrzej Szepietowski |
Inf. Process. Lett. | 1 |