Publicações
PROJETO: Fundamentos da Ciência da Computação:
algoritmos combinatórios e
estruturas discretas --
Projeto Temático ProNEx - FAPESP/CNPq Proc. No. 2003/09925-5
Publicações dos membros do projeto de Julho/2005 a
Junho/2006
Capítulos de Livro
- G. Calinescu and C.G. Fernandes, Maximum Planar Subgraph,
Chapter R43 in Approximation Algorithms and Metaheuristics,
Teofilo F. Gonzalez (Ed.), Francis and Taylor, to appear.
Publicações em
periódicos
- S.S. Adi and C.E. Ferreira, Gene prediction by multiple syntenic
alignment, Journal of Integrative Bioinformatics, v. 13, 2005.
- N. Alon, Y. Kohayakawa, C. Mauduit, C.G. Moreira, and V.
Rödl, Measures of pseudorandomness for finite sequences: minimal
values, Combinatorics, Probability, and Computing, v. 15, n.
1-2, p. 1-29, 2006.
- Egon Balas, and C. C. de Souza, The vertex separator problem: a
polyhedral investigation. Mathematical Programming - Series A,
Volume 103, Issue 3, Jul 2005, Pages 583 - 608
- E. C. Bracht, L. A. A. Meira and F.K. Miyazawa. A greedy
approximation algorithm for the uniform labeling problem. ACM
Journal on Experimental Algorithm. To appear.
- M.H. Carvalho and J. Cheryian. An O(VE) algorithm for ear
decomposition of matching covered graphs. ACM Transactions on
Algorithms, v. 1, n. 2, p. 324-337, 2005
- G. Cintra, F.K. Miyazawa, Y. Wakabayashi, and E.C. Xavier, A
note on the approximability of cutting stock problems, European
Journal of Operational Research, To appear.
- P. Coll, C.C. Ribeiro, and C.C. de Souza, Multiprocessor
schedule under precedence constraints: polyhedral results, Discrete
Applied Mathematics, Volume 154, 770-801, 2006.
- S. Curran, O. Lee and X. Yu, Chain decompositions of 4-connected
graphs, SIAM J. Discr. Math. 19 (2005), 848--880
(electronic).
- S. Curran, O. Lee and X. Yu, Non-separating planar chains in
4-connected graphs, SIAM J. Discr. Math. 19 (2005), 399-419
(electronic).
- R. Dahab, D. Hankerson, F. Hu, M. Long, J. López, A.
Menezes, Software Multiplication using Gaussian Normal Bases, IEEE
Transactions on Computers, to appear.
- C.C. de Souza, and Egon Balas, The vertex separator problem:
algorithms and computations Mathematical Programming - Series A,
Volume 103, Issue 3, Jul 2005, Pages 609 - 631
- N. Eaton, Z. Füredi, A. Kostochka, and J. Skokan, Tree
representations of graphs, European Journal of Combinatorics,
to appear, 17pp.
- C.E. Ferreira, F.M. de Oliveira Filho, New reduction techniques
for the group Steiner tree problem, SIAM Journal on Optimization,
to appear.
- C.E. Ferreira and F.M. de Oliveira Filho, Some formulations for
the group Steiner tree problem, Discrete Applied Mathematics,
to appear, 2006.
- A. Fujita, K.B. Massirer, A.M. Durham, C.E. Ferreira, and M.C.
Sogayar, GATO gene annotation tool for research laboratories, Brazilian
Journal of Medical and Biological Research, Ribeirão Preto,
SP, v. 38, n. 11, 2005.
- Shinya Fujita, Ken-ichi Kawarabayashi, Claudio Leonardo
Lucchesi, Katsuhiro Ota, Michael D. Plummer and Akira Saito. A pair of
forbidden subgraphs and perfect matchings, Journal of
Combinatorial Theory (B), 96 (2006), 315-324.
- S. Gerke, Y. Kohayakawa, V. Rödl, and A. Steger, Small
subsets inherit sparse \epsilon-regularity, Journal of
Combinatorial Theory Series B, to appear, 2006.
- André L. P. Guedes and Lilian Markenzon. Directed
Hypergraph Planarity. Pesquisa
Operacional, 25(3):383-390,
setembro/dezembro 2005.
- P.E. Haxell, T. Luczak, Y. Peng, V. Rödl, A. Rucinski,
M. Simonovits, and J. Skokan, The Ramsey number for hypergraph cycles
I., J. Combin. Theory Ser. A 113(1), 2006, pp. 67-83.
- Juliato, M. ; Araujo, G. C. S. ; Lopez, J. ; Dahab, R. A Custom
Instruction Approach for Hardware and Software Implementations of
Finite Field Arithmetic over F_(2^163) using Gaussian Normal Bases, Journal
of VLSI Processing Systems, accepted for publication.
- K. Kawarabayashi, O. Lee and X. Yu, Non-separating paths with
prescribed ends in 4-connected graphs, Annals of Combinatorics
9 (2005), 47-56.
- S. Kingan and M. Lemos, On weak excluded minors for a class of
graphs, Annals of Combinatorics
9 (2005), 199-204.
- S. Kingan and M. Lemos, On the circuit-cocircuit intersection
conjecture, Graphs and Combinatorics,
to appear.
- M. Lemos, Weight distribuition of the bases of a matroid, Graphs
and Combinatorics 22 (2006), 69-82.
- M. Lemos, Matroids with few non-common bases, Discrete
Mathematics 306 (2006), 680-687.
- M. Lemos and J. Oxley, Matroid packing and covering with circuits
through an element, Journal of
Combinatorial Theory Series B 96 (2006),
135-158.
- M. Lemos, On the number of triangles in 3-connected matroids,
European Journal of Combinatorics,
to appear.
- M. Lemos, Elements belonging to triangles in 3-connected
matroids, Discrete Mathematics,
to appear.
- M. Lemos and T. R. B. Melo, Non-separating cocircuits in
matroids, Discrete Applied
Mathematics, to appear.
- E. Macambira, N. Maculan, and C.C. de Souza, A column generation
approach for SONET ring assignment Networks, Volume 47, Issue
3, 157-171. May 2006.
- E. Macambira, N. Maculan, C. C. de Souza, A note on
characterizing canonical cuts using geometry International
Transactions in Operational Research, (12), 581--593, 2005.
- F.K. Miyazawa and Y. Wakabayashi, Two- and three-dimensional
parametric packing. Computers and Operations Research, to
appear.
- N. Moreano, E. Borin, C. C. de Souza and G. Araujo, Efficient
Datapath Merging for Reconfigurable Architectures IEEE
Transactions on Computer-Aided Design of Integrated Circuits and Systems,
Volume 24, Issue 7, July 2005, pages 969 - 980.
- > V. Rödl and J.Skokan, Applications of the
regularity lemma for uniform hypergraphs, Random Structures and
Algorithms, 28(2), 2006, pp. 180-194.
- M. M. Rodrigues, A. V. Moura, and C. C. de Souza, Vehicle and
Crew Scheduling for Urban Bus Lines European Journal of
Operational Research, Volume 170, Issue 3, 844-862, May 2006.
- E.C. Xavier and F.K. Miyazawa. Approximation Schemes for
Knapsack Problems with Shelf Divisions. Theoretical Computer
Science (Elsevier Science), (352): 71--84, 2006.
- T. H. Yunes, A. V. Moura, and C. C. de Souza, Hybrid Column
Generation Approaches for Urban Transit Crew Management Problems. Transportation
Science, vol. 39, No. 2, 273--288, May 2005.
Publicações em Anais de
Congressos Internacionais
- E. Araújo and J. Soares, Scoring matrices
that induce metrics on sequences, Proceedings of the Latin American
Theoretical Informatics Symposium (Valdivia, Chile, LATIN 2006). Lecture
Notes in Computer Science, v. 3887. p. 68-79.
- J.R. Correa, C.G. Fernandes, and Y. Wakabayashi,
Approximating Rational Objectives is as Easy as Approximating Linear
Ones. In SWAT - 10th Scandinavian Workshop on Algorithm Theory, Riga,
2006. Lecture Notes in Computer Science, v. 4059. p. 351-362.
- Pedro Ribeiro de Andrade Neto and André
L. P. Guedes. A Linear Algorithm for Exact Pattern Matching in
Planar Subdivisions. In Proceedings of SIBGRAPI 2005, XVIII
Simpósio Brasileiro de Computação Gráfica e
Processamento de Imagens, pages 120-127, Natal, RN, 2005.
- D. Dellamonica Jr. and Y. Kohayakawa, An algorithmic
Friedman-Pippenger theorem on tree embeddings and applications to
routing (extended abstract), Proceedings of the 17th Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006. p.
1038-1044.
- C.G. Fernandes, V. Lacroix, and M.-F. Sagot,
Reaction motifs in metabolic networks, Proceedings of the Workshop
on Algorithms in Bioinformatics (Mallorca, Spain, WABI 2005). Lecture
Notes in Computer Science, v. 3692, p. 178-191.
- M. Juliato, G.C.S. Araujo, J. Lopez, J and R. Dahab, A Custom
Instruction Approach for Hardware and Software Implementations of
Finite Field Arithmetic over F_(2^163) using Gaussian Normal Bases, Proceedings.
2005 IEEE International Conference on Field-Programmable Technology,
2005, Cingapura.
- O. Lee and A. Williams. Packing dicycle covers in planar graphs
with no $K_5-e$ minor. Proceedings of the 7th Latin American
Theoretical Informatics Symposium (LATIN'06), Valdivia, Chile. Lecture
Notes in Comp. Science 3887 (2006), 677-688.
- G. Manic and Y. Wakabayashi, Packing triangles in
low-degree graphs and indifference graphs, European Conference on
Combinatorics, Graph Theory, and Applications (EUROCOMB 2005), Berlin,
Germany, September 2005, Berlin, Germany. Discrete Mathematics and
Theoretical Computer Science (DMTCS), vol. AE (2005), pp. 251-256.
- M. Marciniszyn, J. Skokan, R. Spöhel, and A.
Steger, Threshold Functions for Asymmetric Ramsey Properties Involving
Cliques, Proceedings of the 10th International Workshop on
Randomization and Computation, RANDOM 2006, to appear, 12pp.
- J. López and R. Dahab, New Point Compression Algorithms
for Binary Curves. Proceedings of the IEEE Information Theory
Workshop (ITW), 2006, Punta Del Este.
- F.V. Martinez, J.C. de Pina, and J. Soares,
Algorithms for Terminal Steiner Trees, Computing and Combinatorics
Conference (COCOON 2005), Kunming, Yunnan, China, 2005. LNCS 3595,
369-379.
- L.B. Oliveira, H.C. Wong, M. Bern, R. Dahab and A.A.F. Loureiro.
SecLEACH -- A Random Key Distribution Solution for Securing Clustered
Sensor Networks. Accepted for the 5th IEEE International Symposium
on Network Computing and Applications (IEEE NCA06), 2006.
- E.C. Xavier and F.K. Miyazawa. The class constrained bin packing
problem with applications to video-on-demand. 12th Annual International
Computing and Combinatorics Conference (COCOON'06). To appear. Lecture
Notes on Computer Science (LNCS), Springer-Verlag, 2006.
Trabalhos Submetidos
- S.S. Adi and C.E. Ferreira, A graph theoretical
model for the Gene Prediction Problem, 2004.
- D. M. Batista, N. L. S. da Fonseca, F. K.
Miyazawa and F. Granelli. Traffic Engineering for Grid Networks.
- Renato Carmo, Yoshiharu Kohayakawa and Eduardo Laber.
Dois Problemas de Busca.
XIX Concurso de Teses e Dissertações da Sociedade
Brasileira de Computação.
Aceito para publicação nos anais do XXVI Congresso da
Sociedade Brasileira de Computação,
Campo Grande, julho de 2006
- R. Carmo, T. Feder, Y. Kohayakawa, E. Laber, R.
Motwani, Liadan O'Callaghan, Rina Panigrahy, and Dilys Thomas, Querying
priced information in databases: the conjunctive case, 2004.
- V. Cavalcante, A. Lucena, and C.C. de Souza, A relax-and-cut
algorithm to the set partitioning problem.
- G. F. Cintra, F. K. Miyazawa, Y. Wakabayashi and E. C. Xavier.
Algorithms for two-dimensional cutting stock and strip packing problems
using dynamic programming and column generation.
- F. Chataigner, L.R.B. Salgado and Y. Wakabayashi,
Approximability and inapproximability of problems on balanced connected
partitions of graphs, 2006.
- R. Cordovil, B. M. Junior and M. Lemos, The 3-connected binary
matroids with circumference 6 or 7, 2006.
- P. Feofiloff, C.G. Fernandes, C.E. Ferreira, and
J.C. de Pina, Approximation algorithms for the Prize-Collecting Steiner
Tree Problem, 2005.
- C.G Fernandes, O. Lee and Y. Wakabayashi, The Minimum Cycle
Cover and the Chinese Postman Problems on Mixed Graphs with Bounded
Tree Width.
- A. Fujita, J.R. Sato, M.C. Sogayar, C.E. Ferreira,
Non parametric regression and canonical correlation analysis in tumor
classification, 2004.
- B. M. Junior, M. Lemos and T. R. B. Melo, Non-separating circuits
and cocircuits in matroids, 2005.
- S.J. Kim, K. Nakprasit, M. Pelsmajer, and J. Skokan,
Transversal numbers of translates of a convex body, 2006.
- Y. Kohayakawa, V. Rödl, M. Schacht, P.
Sissokho, and J. Skokan, Turán's Theorem for pseudorandom
graphs, 2006.
- G. Manic and Y. Wakabayashi, Packing triangles in
low-degree graphs and indifference graphs, 2005.
- L. A. A. Meira and F. K. Miyazawa. Semidefinite Programming
Based Algorithms for the Ratio Cut Problem.
- A. V. Moura, R. A. Pereira, C. C. de Souza, GRASP strategies for
scheduling activities at oil wells with resource displacement.
- E.M. Rodrigues, M.-F. Sagot and Y. Wakabayashi, The
Maximum Agreement Forest Problem: approximation algorithms and
computational experiments, 2005.
- F.H. Viduani Martinez, J.C. de Pina, and J. Soares, Algorithms
for Terminal Steiner Trees, Theoretical Computer Science, 2006.
- E. C. Xavier and F. K. Miyazawa. A Note on Dual Approximation
Algorithms for Class Constrained Bin Packing Problems.
Outras publicações
- Celso Hartmann, Alexandre Direne, Luis Bona, Fabiano Silva,
Gabriel dos Santos, André Guedes, Marcos Castilho, and Marcos
Sunyé. Linguagem e Ferramenta de Autoria para Promover o
Desenvolvimento de Perícias em Xadrez. In Neide Santos and
Fernanda Campos, editors, XVI SBIE - Simpósio Brasileiro de
Informática na Educação (SBIE-2005), pages
656-665, Juiz de Fora, Brasil, Novembro 2005. SBC-UFJF.
- J. Donadelli, Tópicos em Teoria dos Grafos
- Uma Introdução à Teoria Espectral de Grafos
Notas de aula da disciplina disponível
em http://www.inf.ufpr.br/jair/MANUSCRIPTS/ttg.pdf. Curitiba, 2005.
- J. Donadelli, Algoritmos e Teoria dos Grafos Notas de
aula da disciplina disponível em
http://www.inf.ufpr.br/jair/MANUSCRIPTS/ci065.pdf. Curitiba, 2005.