Andrzej Szepietowski

dblp:96/2354 · DBLP profile ↗
← Back
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
YearPublicationVenuePosition
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 grids
abstract
A 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
STACS1
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
FCT1
1982 A Finite 5-Pebble-Automaton Can Search Every Maze
Andrzej Szepietowski
Inf. Process. Lett.1