Homepage
- Algorithms and data structures
- Graph theory
- Planar graphs, graphs on other surfaces
- Graph coloring
- Approximation algorithms
Publications in MPI database
Published papers
- A Note on Scheduling Equal-Length Jobs to Maximize Throughput,
with M. Chrobak, C. Durr, W. Jawor, M. Kurowski
Short version: Journal on Scheduling, Vol. 9, No. 1, 2006, 71-73.
[BibTeX entry]
[PDF]
Extended version: arXiv.org e-Print archive, cs.DS/0410046, 2004.
[BibTeX entry]
[PS]
[PDF]
- A Generalization of Kotzig's Theorem and its Application,
with Richard Cole, Riste Skrekovski,
Technical Report no. IMFM-(2005)-PS-999,
Institute for Mathematics, Physics and Mechanics in Ljubljana, November
2005.
[BibTeX entry]
[PS]
[PDF]
© SIAM. To appear in SIAM J. Discrete Math.
- Fast 3-Coloring Triangle-Free Planar Graphs,
Proc. 12th Annual European Symposium on Algorithms
(ESA 2004),
LNCS
3221, 2004, 436-447.
[BibTeX entry]
[PS]
[PDF]
© Springer, the original publication is available at www.springerlink.com
Full version (submitted Jan 2005):
[PS]
[PDF]
- More on Light Graphs in 3-Connected Plane Graphs Without
Triangular or Quadrangular Faces,
Technical Report no. 275,
Institute of Informatics, Warsaw University, 2004.
[BibTeX entry]
[PS]
[PDF]
- Short Cycles in Planar Graphs,
Proc. 29th Workshop Graph-Theoretic Concepts in Comp. Sci. (WG
2003),
LNCS
2880, 2003, 284-296.
[BibTeX entry]
[PS]
[PDF]
© Springer, the original publication is available at www.springerlink.com
- Short Path Queries in Planar Graphs in Constant Time,
with M.Kurowski,
Proc.
35th Symp. Theory of
Computing (STOC 2003),
2003, 143-148.
[BibTeX entry]
[PS]
[PDF]
© ACM, the original publication is available at portal.acm.org
- A New 3-Color Criterion For Planar Graphs, with K. Diks and M.
Kurowski,
Proc. 28th Workshop Graph-Theoretic Concepts in Comp. Sci. (WG 2002),
LNCS
2573, 2002, 138-149.
[BibTeX entry]
[PS]
[PDF]
© Springer, the original publication is available at www.springerlink.com
Papers Accepted for Publication in Journals and Conference
Proceedings
- Approximation Scheme for Lowest Outdegree Orientation and Graph
Density Measures
To appear in Proc. 17th International Symposium on Algorithms and
Computation (ISAAC 2006), LNCS, 2006.
[PS]
[PDF]
© Springer, the original publication will be available at www.springerlink.com
- Improved Edge Coloring with Three Colors
To appear in Proc. 32nd Int. Workshop
Graph-Theoretic Concepts in Comp. Sci. (WG 2006) ,
LNCS, 2006.
[PS]
[PDF]
© Springer, the original publication will be available at www.springerlink.com
File [quasi-convex.cpp] contains the program
used to find optimal values of parameters in measure-and-conquer
time complexity proof of the 3-edge-coloring algorithm from the paper.
It is a C++ implementation of the quasi-convex programming algorithm from
the paper D. Eppstein "Quasiconvex Analysis of Backtracking Algorithms",
Proc.
SODA'04, pages 781-790, 2004.
- New Linear-Time Algortihms for Edge-Coloring Planar Graphs,
with Richard Cole
To appear in Algorithmica, (written 2005).
[BibTeX entry]
[PS]
[PDF]
© Springer, the original publication will be available at www.springerlink.com
- Oracles for Bounded Length Shortest Paths in Planar Graphs, with
Maciej
Kurowski
To appear in ACM Transactions on Algorithms, (written 2005).
[BibTeX entry]
[PS]
[PDF]
© ACM, the original publication will be available at portal.acm.org
Papers Submitted to Journals and Conferences
- Adjacency Queries in Dynamic Sparse Graphs
submitted, 2006.
PhD Thesis
Algorytmiczne problemy sciezkowe w grafach planarnych (rozprawa
doktorska),
Algorithmic Path Problems in Planar Graphs (PhD Thesis,
in Polish)
Warsaw University, 2005.
[BibTeX entry]
[PS]
[PDF]
(The thesis is based on papers "Oracles for bounded length shortest paths in
planar graphs", "Fast 3-coloring triangle-free planar graphs" and "Short
cycles in planar graphs")
Other papers
- Spacery po mostach i przejazdzki po miescie,
Software 2.0, 7 / 2002. (in Polish)
You can also see my
dblp record
- October 2001 - May 2005:
Ph. D. student in Computer Science at the Warsaw University, Poland
Title of Ph. D. Thesis: Algorithmic Path Problems for Planar Graphs (supervisor: Prof. Dr. Krzysztof Diks)
- October 1996 - June 2001:
Studies in in Computer Science at the Warsaw University, Poland
Title of Master's Thesis: 3-coloring planar graphs (supervisor: Prof. Dr. Krzysztof Diks)
- October 1996 - June 1999:
Studies in in Mathematics at the Warsaw University, Poland
Title of B. Sc. Thesis: Fractals obtained by Iterated Function Systems
Hobbies
Do you want to climb or run with me? Let me
know!
