Vinícius Gusmão Pereira de Sá  —  Publications

Vinícius Gusmão Pereira de Sá  —  Publicações

Versão em português    English version

Main page

2017   2016   2015   2014   2013   2012   Older

Página principal

2017   2016   2015   2014   2013   2012   +Antigos

  

2017

  1. Dijkstra GraphsPDF DOI Abstract
    Com Lucila Bento, Davidson Boccardo, Raphael Machado, Flávio Miyazawa e Jayme Szwarcfiter.
    With Lucila Bento, Davidson Boccardo, Raphael Machado, Flávio Miyazawa and Jayme Szwarcfiter.
    Discrete Applied Mathematics, no prelo (publicado online em agosto de 2017).
    Discrete Applied Mathematics, to appear (published online in August, 2017).

    We revisit a concept that has been central in some early stages of computer science, that of structured programming: a set of rules that an algorithm must follow in order to acquire a structure that is desirable in many aspects. While much has been written about structured programming, an important issue has been left unanswered: given an arbitrary, compiled program, decide whether it is structured, that is, whether it conforms to the stated principles of structured programming. By employing graph-theoretic tools, we formulate an efficient algorithm for answering this question. To do so, we first introduce the class of graphs which correspond to structured programs, which we call Dijkstra Graphs. Our problem then becomes the recognition of such graphs, for which we present an O(n2)-time algorithm. Furthermore, we describe an isomorphism algorithm for Dijkstra graphs presenting the same quadratic complexity.

  2. Marca d'água estruturadaPDF Abstract
    Com Lucila Bento, Davidson Boccardo, Raphael Machado e Jayme Szwarcfiter.
    With Lucila Bento, Davidson Boccardo, Raphael Machado and Jayme Szwarcfiter.
    Artigo completo submetido em julho de 2017 para publicação em evento.
    Full paper submitted for conference publication in July, 2017.

    Uma marca d'água em artefato digital corresponde a uma informação de identificação embarcada naquele objeto de forma oculta, podendo ser usada para comprovar autoria/propriedade, com o objetivo de desencorajar a pirataria. Dentre as técnicas de marca d'água de software apresentadas na literatura, destacam-se os esquemas baseados em grafos, nos quais uma chave secreta é codificada e inserida no grafo de fluxo de controle do programa. Neste artigo, apresentamos um novo esquema de marca d'água baseado em grafos com duas características principais: nosso algoritmo de codificação emprega aleatoriedade; e, mais importante, nossas marcas d'água estão em conformidade com códigos estruturados. A capacidade de codificar uma mesma chave de distintas formas e a ausência de subestruturas semelhantes a peculiares goto's conferem maior diversidade e furtividade às nossas marcas d'água, tornando-as mais resilientes a ataques de subtração e distorção. Apresentamos também uma implementação em tempo linear.

    A digital object watermark corresponds to embedded identification data which can be timely retrieved to reveal authorship/ownership, with aims at discouraging piracy. Software watermarking schemes based on immersing an encoded key into control flow graphs have been suggested in the literature. We propose a novel graph-based watermarking scheme with two distinctive features: first, our encoding algorithm employs randomization; second, and more importantly, our watermarks conform to structured code. The ability to encode the key in distinct forms and the absence of awkward goto-like substructures lend our watermarks greater diversity and stealthiness, making them more resilient to subtraction and distortion attacks. A linear-time implementation is given.

  3. Robôs de paraquedas: algoritmo randomizado para rendezvous simétrico com marcadoresPDF Abstract
    Com Juan Baptista.
    With Juan Baptista.
    Aceito no XLIX Simpósio Brasileiro de Pesquisa Operacional (SBPO'17, Blumenau/SC, 27-30/08/17).
    Accepted for the XLIX Simpósio Brasileiro de Pesquisa Operacional (SBPO'17, Blumenau/SC, Brazil, August 27-30, 2017).

    Two agents, starting from distinct points and unaware of the position of one another, must meet. This general setting is known in the literature as the Robot Rendezvous Problem. In this paper, we study the symmetric variant of the problem, whereby both agents must execute exactly the same algorithm. The space we consider is one-dimensional, and the starting points of the agents receive markers that may help them during their search. After revisiting the best known solution for the problem, we propose a randomized algorithm that presents a better performance. Furthermore, we analyse the variant in which the agents are required to return to their starting points, where the gain obtained by the randomized strategy is even more pronounced.

    Dois agentes, partindo de pontos distintos e desconhecendo a localização um do outro, precisam se encontrar. Este cenário geral é conhecido na literatura como o Problema do Rendezvous de Robôs. Neste artigo estudamos a variante simétrica do problema, em que os dois agentes devem executar exatamente o mesmo algoritmo. O espaço considerado é unidimensional, e as posições iniciais dos agentes recebem marcadores que podem ajudá-los a se orientar durante a busca. Após revisitarmos a melhor solução conhecida para o problema, propomos uma estratégia de busca randomizada, que apresenta desempenho superior. Analisamos também a variante em que os agentes precisam retornar a seus pontos de origem, e para a qual o ganho da estratégia randomizada é ainda mais acentuado.

  4. Shifting coresets: obtaining linear-time approximations for unit disk graphs and other geometric intersection graphsPDF Abstract
    Com Guilherme Fonseca e Celina Figueiredo.
    With Guilherme Fonseca and Celina Figueiredo.
    Aceito para publicação no International Journal of Computational Geometry & Applications em março de 2017.
    Accepted for publication on the International Journal of Computational Geometry & Applications in March, 2017.

    Numerous approximation algorithms for problems on unit disk graphs have been proposed in the literature, exhibiting a sharp trade-off between running times and approximation ratios. We introduce a variation of the known shifting strategy that allows us to obtain linear-time constant-factor approximation algorithms for such problems. To illustrate the applicability of the proposed variation, we obtain results for three well-known optimization problems. Among such results, the proposed method yields linear-time (4+ε)-approximations for the maximum-weight independent set and the minimum dominating set of unit disk graphs, thus bringing significant performance improvements when compared to previous algorithms that achieve the same approximation ratios. Finally, we use axis-aligned rectangles to illustrate that the same method may be used to derive linear-time approximations for problems on other geometric intersection graph classes.

Voltar ao topo

Back to top

2016

  1. On the embedding of cone graphs in the line with distinct distances between neighborsPDF Abstract
    Com Rodrigo Zhou, Celina Figueiredo e Raphael Machado.
    With Rodrigo Zhou, Celina Figueiredo and Raphael Machado.
    Artigo completo submetido em dezembro de 2016 para publicação em periódico.
    Full paper submitted for journal publication in December, 2016.

    A graph G = (V,E) is graceful if its vertices can be embedded in the interval [0,|E|] in such a way that: (1) all vertices have integer coordinates; (2) no two vertices share the same coordinate; and (3) the distances in the line between two adjacent vertices in the graph are all distinct. We show that the generalized cone graph Cp + Iq (the join of a cycle and an independent set) is graceful for p in {9,13,17} and q≥1. We also show that Cp + Iq is not graceful for several odd values of q with p = 2 (mod 4), disproving a conjecture of Brundage. Our results suggest a conjecture towards the characterization of graceful generalized cone graphs.

  2. On the resilience of canonical reducible permutation graphsPDF DOI Abstract
    Com Lucila Bento, Davidson Boccardo, Raphael Machado e Jayme Szwarcfiter.
    With Lucila Bento, Davidson Boccardo, Raphael Machado and Jayme Szwarcfiter.
    Discrete Applied Mathematics, no prelo (publicado online em novembro de 2016).
    Discrete Applied Mathematics, to appear (published online in November, 2016).

    An ingenious graph-based watermarking scheme recently proposed by Chroni and Nikolopoulos encodes integers as a special type of reducible permutation graphs. It was claimed without proof that those graphs can withstand attacks in the form of a single edge removal. We introduce a linear-time algorithm which restores the original graph after removals of k ≤ 2 edges, therefore proving an even stronger result. Furthermore, we prove that k ≤ 5 general edge modifications (removals/insertions) can always be detected in polynomial time. Both bounds are tight. Our results reinforce the interest in regarding Chroni and Nikolopoulos's scheme as a possible software watermarking solution for numerous applications.

  3. Software control and intellectual property protection in cyber-physical systemsPDF DOI Abstract BibTeX
    Com Davidson Boccardo, Raphael Machado e Jayme Szwarcfiter.
    With Davidson Boccardo, Raphael Machado and Jayme Szwarcfiter.
    EURASIP Journal on Information Security 2016:8 (2016).
    EURASIP Journal on Information Security 2016:8 (2016).

    Software control is a critical issue in cyber-physical systems (CPS): if the expected behavior of the software embedded in a single device of a CPS cannot be enforced then the behavior of the whole CPS may be in jeopardy. Thus, CPS stakeholders like having some level of control over the embedded software. Third-party demands to control the software, however, conflict with the intellectual property protection demanded by software developers, since some level of detail about the software at hand would have to be disclosed. In the present paper we discuss the issue of controlling the software embedded in CPS devices and address the problem of how to achieve an increased level of software control without compromising the protection of intellectual property. We propose a two-party fingerprinting scheme that allows for attribution of responsibility in the case of intellectual property leaks. Our fingerprinting scheme is such that neither party may obtain an advantage over the other by misbehaving, misrepresenting or by prematurely aborting the protocol, therefore providing a fair means to resolve disputes.

    @article{BPS2016,
    	author = {Machado, Raphael Carlos Santos and Boccardo, Davidson Rodrigo and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o and Szwarcfiter, Jayme Luiz},
    	title = {Software control and intellectual property protection in cyber-physical systems},
    	journal = {EURASIP Journal on Information Security},
    	volume = {2016},
    	issue = {8},
    	year = {2016},
    	doi = {10.1186/s13635-016-0032-5}
    } 
         
  4. Cuckoo hashing com perfect rehashPDF poster Abstract
    Com Judismar Arpini Junior.
    With Judismar Arpini Junior.
    Anais do XLVIII Simpósio Brasileiro de Pesquisa Operacional (SBPO'16, Vitória/ES, 27-30/09/16).
    Proceedings of the XLVIII Simpósio Brasileiro de Pesquisa Operacional (SBPO 2016, Vitória/ES, Brazil, September 27-30, 2016).

    Apresentamos uma variante do Cuckoo Hashing tradicional em que o tempo de pior caso para a operação de inserção é O(sqrt(n)), ao contrário do esquema clássico, que, embora bom na média, tem tempo de execução ilimitado no pior caso.

  5. Full characterization of a class of graphs tailored for software watermarkingPDF Abstract
    Com Lucila Bento, Davidson Boccardo, Raphael Machado e Jayme Szwarcfiter.
    With Lucila Bento, Davidson Boccardo, Raphael Machado and Jayme Szwarcfiter.
    Artigo completo submetido em junho de 2016 para publicação em periódico.
    Full paper submitted for journal publication in June, 2016.

    Digital watermarks have been regarded as a promising way to fight copyright violations in the software industry. In some graph-based watermarking schemes, identification data is disguised as control-flow graph of dummy code. Recently, Chroni and Nikolopoulos proposed an ingenious such scheme whereby an integer is encoded into a particular kind of permutation graph. We give a formal characterization of the class of graphs generated by their encoding function, a simpler decoding function, and a robust polynomial-time algorithm which restores watermarks with a constant number of missing edges whenever at all possible, providing a reasonable level of protection against distortive attacks.

  6. Randomized watermarks for structured programsPDF Abstract
    Com Lucila Bento, Davidson Boccardo, Raphael Machado e Jayme Szwarcfiter.
    With Lucila Bento, Davidson Boccardo, Raphael Machado and Jayme Szwarcfiter.
    Livro de abstracts do II Workshop Franco-brasileiro de Grafos e Otimização Combinatória (GCO'16, Praia da Redonda/CE, 28/03-01/04/16).
    Book of abstracts of the II Workshop Franco-brasileiro de Grafos e Otimização Combinatória (GCO'16, Praia da Redonda/CE, Brazil, March 03 - April 04, 2016).

    We propose a new codec for graph-based software watermarking. The encoding algorithm employs randomization to produce distinct watermarks for the same key upon different executions. This feature makes it less likely that a watermark can be spotted by brute force comparisons among different watermarked programs of the same author. Moreover, the dummy code to be injected is structured (as defined by Dijkstra), which distinguishes it from all existing graph-based watermarks we know of, where goto statements are called for.

Voltar ao topo

Back to top

2015

  1. Partial knowledge transfer and almost fair exchange of secretsPDF Abstract
    Com Davidson Boccardo, Raphael Machado e Jayme Szwarcfiter.
    With Davidson Boccardo, Raphael Machado and Jayme Szwarcfiter.
    Artigo completo submetido em setembro de 2015 para publicação em periódico.
    Full paper submitted for journal publication in September, 2015.

    Partial knowledge transfer refers to the ability of proving to a third party that a given sequence of bits belongs of the solution of a problem. This should be done in such a way that the third party can learn strictly nothing but the given sequence. We propose a novel partial knowledge transfer scheme that allows a party to exhibit part of the solution of any problem in NP. The method is then applied to de development of a protocol for a fair exchange of secrets. Our contributions are manifold: 1. We improve the partial knowledge transfer scheme so that it can rely only on the validity of the factoring assumption. 2. We show the equivalence between two variants of the factoring assumption. 3. We devise a partial knowledge transfer scheme that allows to securely exhibit part of the solution of any problem in NP. 4. We propose the use of the improved partial knowledge transfer scheme in an "almost fair" protocol for the exchange of secrets.

  2. O jogo de lógica Sudoku: modelagem teórica, NP-Completude, algoritmos e heurísticasPDF Abstract
    Com Kevin Takano e Rosiane de Freitas.
    With Kevin Takano and Rosiane de Freitas.
    XXXIV Concurso de Trabalhos de Iniciação Científica da Sociedade Brasileira de Computação (CTIC'15, Recife/PE, 20-23/07/15).
    XXXIV Concurso de Trabalhos de Iniciação Científica da Sociedade Brasileira de Computação (CTIC'15, Recife/PE, Brazil, July 20-23, 2015).

    O Sudoku é um problema NP-completo estreitamente relacionado a problemas como satisfatibilidade única, cobertura exata, pré-coloração estendida de vértices e quadrado latino. Estudamos e implementamos as principais técnicas e algoritmos exatos da literatura: enumeração implícita (backtracking com podas), manipulação de bits, dancing links, programação por restrições e programação inteira. Nossa principal contribuição está em dois novos métodos: um exato, baseado em propagação de restrições e com melhor desempenho do que os similares encontrados na literatura, e um meta-heurístico GRASP para o Sudoku genérico n x n. São também propostos algoritmos polinomiais para o caso particular do grid inicialmente vazio, com aplicação na geração de instâncias do Sudoku em níveis variados de dificuldade.

    We tackle the mathematical and computational aspects of the logic puzzle Sudoku. The Sudoku is an NP-complete problem which bears a strong connection with problems such as unique satisfiability, exact cover, vertex pre-coloring extension, and Latin square. We have studied and implemented the main techniques and exact algorithms from the literature, to wit: implicit enumeration (backtracking with pruning), bit manipulation, dancing links, constraint programming, and integer programming. Our main contribution comes in the form of two new methods: an exact method, based on constraint propagation, with better performance than similar ones from the literature; and a GRASP metaheuristic method for the generic n x n Sudoku. We also propose polynomial-time algorithms for the particular case of the initially empty grid, which suit well the generation of Sudoku instances in varying levels of difficulty.

  3. Fair fingerprinting protocol for attesting software misusesPDF Abstract
    Com Davidson Boccardo, Raphael Machado e Jayme Szwarcfiter.
    With Davidson Boccardo, Raphael Machado and Jayme Szwarcfiter.
    Anais do X International Conference on Availability, Reliability and Security (ARES'15, Toulouse, França, 24-28/08/15).
    Proceedings of the 10th International Conference on Availability, Reliability and Security (ARES'15, Toulouse, France, August 24-28, 2015).

    Digital watermarks embed information into a host artifact in such a way that the functionalities of the artifact remain unchanged. Allowing for the timely retrieval of authorship/ownership information, and ideally hard to be removed, watermarks discourage piracy and have thus been regarded as important tools to protect the intellectual property. A watermark aimed at uniquely identifying an artifact is referred to as a fingerprint. After presenting a formal definition of digital watermarks, we introduce an unbiased fingerprinting protocol—based on oblivious transfer—that lends no advantage to the prosecuting party in a dispute around intellectual property breach.

  4. Near-linear-time algorithm for the geodetic Radon number of gridsPDF DOI Abstract BibTeX
    Com Mitre Dourado, Dieter Rautenbach e Jayme Szwarcfiter.
    With Mitre Dourado, Dieter Rautenbach and Jayme Szwarcfiter.
    Discrete Applied Mathematics 210 (2016), 277-283.
    Discrete Applied Mathematics 210 (2016), 277-283.

    The Radon number of a graph is the minimum integer r such that all sets of at least r of its vertices can be partitioned into two subsets whose convex hulls intersect. Determining the Radon number of general graphs in the geodetic convexity is NP-hard. In this paper, we show the problem is polynomial for d-dimensional grids, for all d ≥ 1. The proposed algorithm runs in near-linear O(d (log d)1/2) time for grids of arbitrary sizes, and in sublinear O(log d) time when all grid dimensions have the same size.

    @article{BPS2016,
    	author = {Dourado, Mitre Costa and Rautenbach, Dieter and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o and Szwarcfiter, Jayme Luiz},
    	title = {Near-linear-time algorithm for the geodetic Radon number of grids},
    	journal = {Discrete Applied Mathematics},
    	volume = {210},
    	year = {2016},
    	doi = {10.1016/j.dam.2015.05.001}
    } 
         
  5. The graphs of Structured ProgrammingPDF Abstract
    Com Lucila Bento, Davidson Boccardo, Raphael Machado e Jayme Szwarcfiter.
    With Lucila Bento, Davidson Boccardo, Raphael Machado and Jayme Szwarcfiter.
    Anais do XIII Cologne-Twente Workshop on Graphs & Combinatorial Optimization (CTW'15, Istanbul, Turquia, 26-28/05/15).
    Proceedings of the XIII Cologne-Twente Workshop on Graphs & Combinatorial Optimization (CTW'15, Istanbul, Turquia, May 26-28, 2015).

    Control flow graphs represent the possible execution paths of a program and can be obtained by static analysis of software binaries. We give a formal characterization of the subclass of control flow graphs that correspond to structured code.

  6. Some illustrative examples on the use of hash tablesPDF DOI 1-page sample Abstract BibTeX
    Com Lucila Bento e Jayme Szwarcfiter.
    With Lucila Bento and Jayme Szwarcfiter.
    Pesquisa Operacional, 35 2 (2015), 1-15.
    Pesquisa Operacional, 35 2 (2015), 1-15.

    Hash tables are among the most important data structures known to mankind. Through hashing, the address of each stored object is calculated as a function of the object's contents. Because they do not require exorbitant space and, in practice, allow for constant-time dictionary operations (insertion, lookup, deletion), hash tables are often employed in the indexation of large amounts of data. Nevertheless, there are numerous problems of somewhat different nature that can be solved in elegant fashion using hashing, with significant economy of time and space. The purpose of this paper is to reinforce the applicability of such technique in the area of Operations Research and to stimulate further reading, for which adequate references are given. To our knowledge, the proposed solutions to the problems presented herein have never appeared in the literature, and some of the problems are novel themselves.

    @article{BPS2015,
    	author = {Bento, Lucila Maria de Souza, and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o and Szwarcfiter, Jayme Luiz},
    	title = {Some illustrative examples on the use of hash tables},
    	journal = {Pesquisa Operacional},
    	volume = {35},
    	issue = {2},
    	pages = {1--15},
    	year = {2015},
    	issn = {1678-5142},
    	doi = {10.1590/0101-7438.2015.035.02.001}
    } 
         

            1-page sample

Voltar ao topo

Back to top

2014

  1. Algoritmos certificadores e verificadores: testemunhas ausentes e provas computacionaisPDF Abstract
    Com Anne Federici Marinho.
    With Anne Federici Marinho.
    Livro de Abstracts do VI Latin-American Workshop on Cliques in Graphs (LAWCG'14, Pirenópolis/GO, Brasil, 09-12/11/14).
    Book of Abstracts of the 6th Latin-American Workshop on Cliques in Graphs (LAWCG'14, Pirenópolis/GO, Brasil, November 09-12, 2014).

    Um algoritmo certificador para um problema Π exibe, para uma instância x de Π, uma resposta y e uma testemunha w, possibilitando a verificação da corretude da resposta por meio de um algoritmo verificador, que recebe x, y e w como entrada. Algoritmos certificadores são em muitos casos preferíveis a algoritmos tradicionais (não-certificadores) porque permitem que acatemos as respostas obtidas como verdadeiras sem que precisemos confiar cegamente na implementação dos algoritmos que as encontraram, garantindo que as respostas não foram comprometidas por falhas na implementação. Na literatura sobre algoritmos certificadores, busca-se em geral possibilitar uma verificação simples, de forma que a corretude do próprio verificador possa ser trivialmente comprovada, e eficiente, permitindo que a resposta seja verificada a partir da testemunha fornecida sem aumento significativo do tempo total de processamento. Há, no entanto, dois casos que fogem a esse padrão e que apresentam, ainda assim, interesse do ponto de vista de certificação/verificação. O primeiro caso é aquele em que conseguimos construir verificadores que prescindem de testemunhas, pois são capazes de efetuar a verificação de forma simples e eficiente diretamente da resposta obtida. O segundo é o caso em que a testemunha exibida permite uma verificação que não é formalmente eficiente, por demandar tempo exponencial, mas que, para instâncias pequenas, é computacionalmente viável, permitindo por exemplo a criação de provas computacionais para teoremas. Ilustramos os dois casos acima, respectivamente, com algoritmos verificadores para o problema da seleção dos k maiores elementos e o problema de reconhecimento de grafos de disco unitário.

    @inproceedings{FMS14,
    	author = {Federici Marinho, Anne Rose Alves and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o},
    	title = {Algoritmos certificadores e verificadores: testemunhas ausentes e provas computacionais},
    	booktitle = {Book of Abstracts of the 6th Latin-American Workshop on Cliques in Graphs (LAWCG'14)},
    	year = {2014},
    }
            
  2. Grafos de Permutação Redutíveis Canônicos: caracterização, reconhecimento e aplicação a marcas d'água digitaisPDF Abstract
    Com Lucila Bento, Davidson Boccardo, Raphael Machado e Jayme Szwarcfiter.
    With Lucila Bento, Davidson Boccardo, Raphael Machado e Jayme Szwarcfiter.
    Livro de Abstracts do VI Latin-American Workshop on Cliques in Graphs (LAWCG'14, Pirenópolis/GO, Brasil, 09-12/11/14).
    Book of Abstracts of the 6th Latin-American Workshop on Cliques in Graphs (LAWCG'14, Pirenópolis/GO, Brasil, November 09-12, 2014).

    Um grafo de fluxo redutível G = (V, E, s) é um grafo direcionado com uma fonte sV(G), tal que, para cada ciclo C de G, todo caminho direcionado de s a C chega a C pelo mesmo vértice de C. Diversas pesquisas na área de proteção de software desenvolvidas recentemente estão relacionadas a uma subclasse dos grafos de fluxo redutíveis, chamada de grafos de permutação redutíveis. Tais grafos possuem, entre outras características, caminho hamiltoniano único. Neste trabalho, apresentamos uma caracterização de uma subclasse dos grafos de permutação redutíveis chamada grafos de permutação redutíveis canônicos. Como consequência dessa caracterização, que é baseada em propriedades estruturais, obtivemos um algoritmo linear de reconhecimento. Grafos de permutação redutíveis canônicos podem ser utilizados para codificar marcas d'água digitais, e correspondem de fato aos grafos gerados pelo algoritmo de codificação de marcas d'água apresentado por Chroni e Nikolopoulos no COMPSAC'12. Além da caracterização e do reconhecimento de tais grafos, apresentamos um algoritmo polinomial que recupera, sempre que possível, um grafo da classe com um número constante de arestas removidas, e também um algoritmo linear para restaurar grafos de permutação redutíveis canônicos com até duas arestas removidas — o que provamos ser sempre possível.

    @inproceedings{BBMSS14,
    	author = {Bento, Lucila Maria de Souza and Boccardo, Davidson and Machado, Raphael Machado Santos and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o and Szwarcfiter, Jayme Luiz},
    	title = {Grafos de Permuta\c c\ão Redut\'iveis Can\^onicos:
                   caracteriza\c c\~ao, reconhecimento e aplica\c c\~ao a marcas d'\'agua digitais},
    	booktitle = {Book of Abstracts of the 6th Latin-American Workshop on Cliques in Graphs (LAWCG'14)},
    	year = {2014},
    }
            
  3. A randomized graph-based scheme for software watermarkingPDF Abstract
    Com Lucila Bento, Davidson Boccardo, Raphael Machado e Jayme Szwarcfiter.
    With Lucila Bento, Davidson Boccardo, Raphael Machado and Jayme Szwarcfiter.
    Anais do XIV Simpósio Brasileiro de Segurança da Informação e de Sistemas Computacionais (SBSEG'14, Belo Horizonte/MG, 3-6/11/14).
    Proceedings of the XIV Simpósio Brasileiro de Segurança da Informação e de Sistemas Computacionais (SBSEG'14, Belo Horizonte/MG, Brazil, November 3-6, 2014).

    The insertion of watermarks into proprietary objects is an old means of discouraging piracy. It works by embedding into the object some (often surreptitious) data meant to disclose authorship/ownership. Some promising graph-based watermarking schemes to protect the intellectual property of software have been suggested in the literature, and recent efforts have been endeavored to improve their resilience to attacks. Among the pursued attributes of software watermarking solutions is the one referred to as "diversity", which is the ability to encode the intended information in many distinct forms, making it harder for an attacker to find and remove it. We propose a graph-based scheme which achieves a high level of diversity through randomization, while admitting an efficient, linear-time implementation nonetheless.

    A inserção de marcas d'água em objetos proprietários é uma conhecida maneira de se desencorajar pirataria. Funciona através da inclusão de alguma informação (em geral escondida) que permita revelar autoria ou propriedade do objeto. Alguns esquemas de marca d'áagua baseados em grafos para proteger a propriedade intelectual de programas de computador têm sido sugeridos na literatura, e esforços recentes têm sido devotados ao aumento de sua resiliência a ataques. Entre os atributos buscados para soluções de marca d'água de programas está a chamada "diversidade", que é a habilidade de codificar a informação desejada de várias maneiras distintas, tornando mais difícil sua localização e remoção por parte do atacante. Apresentamos um esquema baseado em grafos que consegue, através de randomização, um alto grau de diversidade, permitindo, ainda assim, uma implementação eficiente em tempo linear.

  4. Protocolo para transferência parcial de conhecimento e sua aplicação à verificação segura de marcas d'águaPDF Abstract
    Com Davidson Boccardo, Raphael Machado e Jayme Szwarcfiter.
    With Davidson Boccardo, Raphael Machado and Jayme Szwarcfiter.
    Anais do XIV Simpósio Brasileiro de Segurança da Informação e de Sistemas Computacionais (SBSEG'14, Belo Horizonte/MG, 3-6/11/14).
    Proceedings of the XIV Simpósio Brasileiro de Segurança da Informação e de Sistemas Computacionais (SBSEG'14, Belo Horizonte/MG, Brazil, November 3-6, 2014).

    Let y=f(x) for some one-way function f. We present a simple algorithm that allows that the bits of x are but partially exhibited in a demonstration, through a zero-knowledge proof scheme, that x is indeed an element of the pre-image of y under f. As an application, we show that it is possible to disclose a watermark embedded into a digital artifact without the need of revealing its location. The result is a secure verification protocol for software watermarking which does not increase the likelihood that an attacker is successful in a removal attack.

    Seja y=f(x) para uma função one-way f. Apresentamos um algoritmo simples que permite exibir a terceiros apenas parte dos bits de x numa demonstração, por meio de um esquema de prova de conhecimento nulo, de que x pertence de fato à pré-imagem de y sob f. Como aplicação, mostramos que é possível exibir uma marca d'água embarcada em um artefato digital sem necessidade de revelar sua localização. O resultado é um protocolo seguro para verificação de marcas d'água de software que não aumenta a probabilidade de um atacante ser bem-sucedido em um ataque de remoção.

  5. On the recognition of unit disk graphs and the Distance Geometry Problem with RangesPDF DOI Abstract BibTeX
    Com Guilherme Fonseca, Celina Figueiredo e Raphael Machado.
    With Guilherme Fonseca, Celina Figueiredo and Raphael Machado.
    Discrete Applied Mathematics 197 (2015), 3-19.
    Discrete Applied Mathematics 197 (2015), 3-19.

    We introduce a method to decide whether a graph G admits a realization on the plane in which two vertices lie within unitary distance from one another exactly if they are neighbors in G. Such graphs are called unit disk graphs, and their recognition is a known NP-hard problem. By iteratively discretizing the plane, we build a sequence of geometrically defined trigraphs—graphs with mandatory, forbidden and optional adjacencies—until either we find a realization of G or the interruption of such sequence certifies that no realization exists. Additionally, we consider the proposed method in the scope of the more general Distance Geometry Problem with Ranges, where arbitrary intervals of pairwise distances are allowed.

    @article{FSMF14,
    	author = {da Fonseca, Guilherme Dias and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o and Machado, Raphael Carlos Santos and de Figueiredo, Celina Miraglia Herrera},
    	title = {On the recognition of unit disk graphs and the Distance Geometry Problem with Ranges},
    	journal = {Discrete Applied Mathematics},
    	volume = {197},
    	pages = {3--19},
    	year = {2015},
    	issn = {0166-218X},
    	doi = {10.1016/j.dam.2014.08.014}
    } 
            
  6. Linear-time approximation algorithms for unit disk graphsPDF arXiv slides Abstract BibTeX
    Com Guilherme Fonseca e Celina Figueiredo.
    With Guilherme Fonseca and Celina Figueiredo.
    Anais do 12th Workshop on Approximation and Online Algorithms (WAOA'14, Breslávia, Polônia, 8-12/09/14),
    Lecture Notes in Computer Science 8952 (2015), 132-143.
    Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA'14, Wroclaw, Poland, September 8-12, 2014),
    Lecture Notes in Computer Science 8952 (2015), 132-143.

    Numerous approximation algorithms for unit disk graphs have been proposed in the literature, exhibiting sharp trade-offs between running times and approximation ratios. We propose a method to obtain linear-time approximation algorithms for unit disk graph problems. Our method yields linear-time (4+ε)-approximations to the maximum-weight independent set and the minimum dominating set, as well as a linear-time approximation scheme for the minimum vertex cover, bringing dramatic performance improvements when compared to previous algorithms that achieve the same approximation factors.

    @incollection{FSF14,
    	author = {da Fonseca, Guilherme Dias and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o and de Figueiredo, Celina Miraglia Herrera},
    	title = {Linear-time approximation algorithms for unit disk graphs},
    	booktitle = {Approximation and Online Algorithms},
    	editor = {Bampis, E. and Svensson, O.},
    	publisher = {Springer International Publishing Switzerland},
    	series = {Lecture Notes in Computer Science},
    	volume = {7846},
    	isbn = {978-3-642-38015-0},
    	doi = {10.1007/978-3-319-18263-6_12},
    	pages = {132--143},
    	year = {2015},
    }
            
  7. Minimizando ramificações em árvores geradorasPDF Abstract BibTeX
    Com Adalton Sena e Loana Nogueira.
    With Adalton Sena and Loana Nogueira.
    Anais do XLVI Simpósio Brasileiro de Pesquisa Operacional (SBPO'14, Salvador/BA, 16-19/09/14).
    Proceedings of the XLVI Simpósio Brasileiro de Pesquisa Operacional (SBPO 2014, Salvador/BA, Brazil, September 16-19, 2014).

    Embora não se conheçam algoritmos eficientes para resolvê-los, problemas NP-difíceis estão com frequência presentes em situações reais que demandam solução, justificando o interesse por abordagens heurísticas e algoritmos aproximativos. Uma dessas situações é a da alocação de switches WDM (Wave-Length Division Multiplexing) em redes óticas. Tais switches são dispositivos sofisticados e caros, portanto minimizar sua quantidade em uma rede torna-se desejável. O problema em que estamos interessados pode ser modelado formalmente como se segue: dado um grafo conexo G, encontrar uma árvore geradora T de G que possua a menor quantidade possível de ramificações, ou seja, que minimize o número de vértices v com grau dT(v) ≥ 3. Apresentamos novas heurísticas para o problema, conseguindo resultados superiores aos obtidos por aquelas anteriormente propostas na literatura.

    Although there are no known efficient algorithms for solving NP-hard problems, such problems frequently arise in practical situations which demand best-effort solutions, hence the interest in approximation algorithms and heuristic-based approaches. One of these situations is the allocation of WDM (Wave-Length Division Multiplexing) switches in optical networks. Such devices are quite expensive, therefore it is an important task to minimize their number in the network. The problem we are interested in can be formally described as follows: given a connected graph G, find a spanning tree Tof G which presents the smallest number of branches, i.e., vertices v with degree dT(v) ≥ 3. We introduce novel heuristics for the problem, obtaining better results when compared to those previously proposed in the literature.

    @inproceedings{SNS2014,
    	author = {Almeida, Adalton Sena and Nogueira, Loana Tito, and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o},
    	title = {Minimizando ramifica{\c c}{\~o}es em {\'a}rvores geradoras},
    	booktitle = {Anais do XLVI Simp{\'o}sio Brasileiro de Pesquisa Operacional (SBPO'13)},
    	url = {http://www.sbpo2014.iltc.br/pdf/128504.pdf},
    	year = {2014},
    }
            
  8. Cripto-esteganografia: imagens inocentes podem transportar arquivos secretosPDF poster Abstract
    Com Vitor Costa.
    With Vitor Costa.
    Anais do XXXV Congresso Nacional de Matemática Aplicada e Computacional (CNMAC'14, Natal/RN, Brazil, 08-12/09/14).
    Proceedings of the XXXV Congresso Nacional de Matemática Aplicada e Computacional (CNMAC'14, Natal/RN, Brazil, September 08-12, 2014).

    Mostramos como guardar uma informação qualquer dentro de uma imagem, e como deixá-la protegida através de criptografia. Nosso método é original e de simples implementação, podendo ser utilizado tanto para uso pessoal quanto para a troca de mensagens e arquivos através de uma rede insegura.

  9. Heurística para o passeio aberto do cavalo em tabuleiros multidimensionaisPDF poster Abstract
    Com Vitor Costa.
    With Vitor Costa.
    Anais do XXXV Congresso Nacional de Matemática Aplicada e Computacional (CNMAC'14, Natal/RN, Brazil, 08-12/09/14).
    Proceedings of the XXXV Congresso Nacional de Matemática Aplicada e Computacional (CNMAC'14, Natal/RN, Brazil, September 08-12, 2014).

    Propomos uma heurística linear para a determinação de um passeio aberto do cavalo em tabuleiros multidimensionais a partir de qualquer casa inicial plausível. Nos casos em que duas das dimensões têm tamanho n, para algum n par maior ou igual a 5, a heurística funcionou em 100% dos casos testados (5 <= n <= 5000).

  10. Blind-friendly von Neumann's heads or tailsPDF DOI slides 1-page sample Abstract BibTeX
    Com Celina Figueiredo.
    With Celina Figueiredo.
    The American Mathematical Monthly 121 7 (2014), 600-609.
    The American Mathematical Monthly 121 7 (2014), 600-609.

    The toss of a coin is usually regarded as the epitome of randomness, and has been used for ages as a means to resolve disputes in a simple, fair way. Perhaps as ancient as consulting objects such as coins and dice is the art of maliciously biasing them in order to unbalance their outcomes. However, it is possible to employ a biased device to produce equiprobable results in a number of ways, the most famous of which is the method suggested by von Neumann back in 1951. This paper addresses how to extract uniformly distributed bits of information from a nonuniform source. We study some probabilities related to biased dice and coins, culminating in an interesting variation of von Neumann's mechanism that can be employed in a more restricted setting where the actual results of the coin tosses are not known to the contestants.

    @article{SF14,
    	author = {Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o, and de Figueiredo, Celina Miraglia Herrera},
    	title = {Blind-friendly von Neumann's heads or tails},
    	journal = {The American Mathematical Monthly},
    	volume = {121},
    	issue = {7},
    	pages = {600--609},
    	year = {2014},
    	issn = {0002-9890},
    	doi = {10.4169/amer.math.monthly.121.07.600}
    } 
            

            1-page sample

  11. Efficient sub-5 approximations for minimum dominating sets in unit disk graphsPDF DOI arXiv 1-page sample Abstract BibTeX
    Com Guilherme Fonseca, Celina Figueiredo e Raphael Machado.
    With Guilherme Fonseca, Celina Figueiredo and Raphael Machado.
    Theoretical Computer Science 540-541 (2014), 70-81.
    Theoretical Computer Science 540-541 (2014), 70-81.

    A unit disk graph is the intersection graph of n congruent disks on the plane. Dominating sets in unit disk graphs are widely studied due to their application in wireless ad-hoc networks. Because the minimum dominating set problem for unit disk graphs is NP-hard, numerous approximation algorithms have been proposed in the literature, including some PTAS. However, since the proposal of a linear-time 5-approximation algorithm in 1995, the lack of efficient algorithms attaining better approximation factors has aroused attention. We introduce a linear-time O(n+m) approximation algorithm that takes the usual adjacency representation of the graph as input and outputs a 44/9-approximation. This approximation factor is also attained by a second algorithm, which takes the geometric representation of the graph as input and runs in O(n log n) time regardless of the number of edges. Additionally, we propose a 43/9-approximation which can be obtained in O(n2m) time given only the graph's adjacency representation. It is noteworthy that the dominating sets obtained by our algorithms are also independent sets.

    @article{FFMS14,
    	author = {da Fonseca, Guilherme Dias and de Figueiredo, Celina Miraglia Herrera and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o and Machado, Raphael Carlos Santos},
    	title = {Efficient sub-5 approximations for minimum dominating sets in unit disk graphs},
    	journal = {Theoretical Computer Science},
    	volume = {540--541},
    	issue = {},
    	pages = {70--81},
    	year = {2014},
    	issn = {0304-3975},
    	doi = {10.1016/j.tcs.2014.01.023}
    } 
            

            1-page sample

Voltar ao topo

Back to top

2013

  1. Fingerprinting de software e aplicações à Metrologia LegalPDF Abstract BibTeX
    Com Lucila Bento, Davidson Boccardo, Rafael Costa, Raphael Machado e Jayme Szwarcfiter.
    With Lucila Bento, Davidson Boccardo, Rafael Costa, Raphael Machado and Jayme Szwarcfiter.
    Anais do 10th International Congress on Electrical Metrology (SEMETRO'13, Buenos Aires, Argentina, 25-27/09/13).
    Proceedings of the 10th International Congress on Electrical Metrology (SEMETRO'13), Buenos Aires, Argentina, September 25-27, 2013).

    O termo fingerprinting refere-se ao ato de embarcar uma informação em um objeto com o objetivo de torná-lo posteriormente rastreável. Neste trabalho, propomos uma aplicação de fingerprinting à Metrologia Legal. Consideramos o modelo de validação de instrumentos de medição que envolve uma etapa de análise de software, e propomos o uso de uma técnica de fingerprinting na construção de um protocolo de segurança que permite identificar responsáveis por eventuais "vazamentos de código". A técnica utilizada emprega fingerprinting baseado em grafos, que são estruturas combinatórias naturalmente associadas ao fluxo de execução de um programa.

    @inproceedings{BBCMSS13,
    	author = {Bento, Lucila Maria de Souza and Boccardo, Davidson and Costa, Rafael and Machado, Raphael Machado Santos and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o and Szwarcfiter, Jayme Luiz},
    	title = {Fingerprinting de software e aplica{\c c}{\~o}es {\`a} Metrologia Legal},
    	booktitle = {Proceedings of the 10th International Congress on Electrical Metrology (SEMETRO'13)},
    	year = {2013},
    }
            
  2. Heurística eficiente para o passeio aberto do cavalo a partir de casas arbitrárias em tabuleiros quadradosPDF Abstract BibTeX
    Com Vitor Costa.
    With Vitor Costa.
    Anais do XLV Simpósio Brasileiro de Pesquisa Operacional (SBPO'13, Natal/RN, 16-19/09/13).
    Proceedings of the XLV Simpósio Brasileiro de Pesquisa Operacional (SBPO 2013, Natal/RN, Brazil, September 16-19, 2013).

    Não se conhece algoritmo exato eficiente para o célebre problema do passeio aberto do cavalo em tabuleiros de xadrez. A heurística proposta recentemente por Álvarez-Martínez e Lázaro (em Algoritmo determinístico para resolver el problema del tour abierto del caballo sobre tableros de ajedrez n × n, SBPO 2012) apresenta bons resultados. Entretanto, há contra-exemplos de diversos tamanhos para a afirmação de que ela seria capaz de encontrar solução a partir de todas as possíveis casas iniciais. Além disso, ela não lida bem com as simetrias naturais do problema, podendo encontrar resultados divergentes partindo de casas iniciais absolutamente simétricas. A partir de um refinamento baseado nos octantes do tabuleiro, apresentamos uma heurística simétrica que obteve êxito em todos os testes realizados (tabuleiros n × n, para 5 ≤ n430, de todas as possíveis casas iniciais). Ademais, a heurística proposta se mostra extensível a tabuleiros retangulares e multidimensionais.

    No efficient exact algorithm is known for the famous open knight's tour problem over a chessboard. The heuristic method proposed recently by Álvarez-Martínez e Lázaro (em Algoritmo determinístico para resolver el problema del tour abierto del caballo sobre tableros de ajedrez n × n, SBPO 2012) presents good results. However, there are counterexamples of various sizes for its alleged ability to find a solution starting from every possible starting position. Besides that, it does not cope well with the natural symmetries of the problem, at times producing diverging results for absolutely symmetrical initial squares. A refinement based upon the octants of the chessboard gave rise to a symmetry-preserving method that was successful in n × n chessboards, for 5 ≤ n ≤ 430, starting from all possible initial squares. Moreover, the proposed method is probably extensible to rectangular and multidimensional boards.

    @inproceedings{CS13,
    	author = {Costa, Vitor Silva and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o},
    	title = {Heur{\'i}stica eficiente para o passeio aberto do cavalo a partir de casas arbitr{\'a}rias em tabuleiros quadrados},
    	booktitle = {Anais do XLV Simp{\'o}sio Brasileiro de Pesquisa Operacional (SBPO'13)},
    	url = {http://www.sbpo2013.iltc.br/pdf/115564.pdf},
    	year = {2013},
    }
            
  3. Proteção de software por marcas d'água baseadas em grafosPDF slides Abstract BibTeX
    Com Lucila Bento, Davidson Boccardo, Raphael Machado e Jayme Szwarcfiter.
    With Lucila Bento, Davidson Boccardo, Raphael Machado and Jayme Szwarcfiter.
    Anais do 40º Seminário Integrado de Software e Hardware (SEMISH'13, Maceió/AL, Brasil, 23-26/07/13).
    Proceedings of the 40th Seminário Integrado de Software e Hardware (SEMISH'13), Maceió/AL, Brazil, July 23-26, 2013).

    A inserção de marcas d'água em programas de computador objetiva a posterior identificação de sua autoria ou propriedade, desencorajando a cópia ilegal dos mesmos. Neste artigo, consideramos o esquema de marcas d'água baseadas em grafos proposto por Chroni e Nikolopoulos (An efficient graph codec system for software watermarking, COMPSAC'12), e formulamos dois algoritmos robustos, com complexidades e aplicabilidades distintas, para a restauração de uma marca d'água da qual k > 0 arestas foram maliciosamente removidas. Ademais, estudamos a resiliência do esquema considerado diante desse tipo de ataque, e apresentamos resultados computacionais evidenciando que a probabilidade de uma marca d'água se tornar irrecuperável pela remoção de um número k fixo de arestas tende a zero à medida em que o tamanho da marca d'água aumenta.

    The insertion of watermarks into computer programs allows for the timely retrieval of authorship/ownership information, therefore discouraging software piracy. In this paper, we consider the graph-based watermarking scheme proposed by Chroni and Nikolopoulos (An efficient graph codec system for software watermarking, COMPSAC'12}), and we formulate robust algorithms to restore a watermark from which k > 0 edges were maliciously removed. Moreover, we study the resilience of the considered scheme face to such kind of attack, and we present computational results indicating that the probability that a watermark cannot be restored after the removal of a fixed number k of edges tends to zero as the size of the watermark grows.

    @inproceedings{BBMSS13b,
    	author = {Bento, Lucila Maria de Souza and Boccardo, Davidson and Machado, Raphael Carlos Santos and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o and Szwarcfiter, Jayme Luiz},
    	title = {Prote{\c c}{\~a}o de software por marcas d'{\'a}gua baseadas em grafos},
    	booktitle = {Anais do XL Semin{\'a}rio Integrado de Software e Hardware (SEMISH'13)},
    	volume = {(forthcoming)},
    	year = {2013},
    }
            
  4. A geometric trigraph model for unit disk graph recognitionPDF poster Abstract BibTeX
    Com Guilherme Fonseca, Raphael Machado e Celina Figueiredo.
    With Guilherme Fonseca, Raphael Machado and Celina Figueiredo.
    Anais do Workshop on Distance Geometry and Applications (DGA'13, Manaus/AM, Brasil, 24-27/06/13).
    Proceedings of the Workshop on Distance Geometry and Applications (DGA'13, Manaus/AM, Brazil, June 24-27, 2013).

    A unit disk graph G is a graph whose vertices can be mapped to points on the plane and whose edges are defined by pairs of points within unitary Euclidean distance from one another. The recognition of unit disk graphs is no easy feat. Indeed, the fastest known algorithm to decide whether a given graph is a unit disk graph is doubly exponential. In this paper, we introduce a practical algorithm to produce certified answers to the question "is G a unit disk graph?" in either way, for any given graph G. By imposing that the points' coordinates belong to discrete sets of increasing granularity, our method builds a sequence of trigraphs G'i, i.e. graphs with mandatory and optional edges, until a certain G'i is found possessing properties that allow us to state that G is a unit disk graph, or the sequence of trigraphs is interrupted, whereupon we are able to state that G is not a unit disk graph. We remark that the proposed method was actually implemented, and were able to produce our first YES/NO certificates for some small graphs.

    @inproceedings{FSMF13,
    	author = {da Fonseca, Guilherme Dias and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o and Machado, Raphael Carlos Santos and de Figueiredo, Celina Miraglia Herrera},
    	title = {A geometric trigraph model for unit disk graph recognition},
    	booktitle = {Proceedings of the Workshop on Distance Geometry and Applications (DGA'13)},
    	year = {2013},
    }
            
  5. Towards a provably resilient scheme for graph-based watermarkingPDF arXiv slides Abstract BibTeX
    Com Lucila Bento, Davidson Boccardo, Raphael Machado e Jayme Szwarcfiter.
    With Lucila Bento, Davidson Boccardo, Raphael Machado and Jayme Szwarcfiter.
    Anais do 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'13, Lübeck, Alemanha, 19-21/06/13),
    Lecture Notes in Computer Science 8165 (2013), 50-63.
    Proceedings of the 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'13, Lübeck, Germany, June 19-21, 2013),
    Lecture Notes in Computer Science 8165 (2013), 50-63.

    Techniques of watermarking/fingerprinting concern the embedding of identification data into a digital object, allowing for later claims of authorship/ownership and therefore discouraging piracy. Graph-based watermarking schemes comprise an encoding algorithm, which translates a given number (the identifier, usually a positive integer) onto some appropriately tailored graph (the watermark), and a decoding algorithm, which extracts the original identifier from a given watermark. Collberg, Kobourov, Carter and Thomborson (Error-correcting graphs for software watermarking, WG'03) introduced one such scheme, meant for software watermarking, in which an integer key was encoded onto a reducible permutation graph. A number of interesting ideas have further improved the original scheme, including the formulation of a particularly promising linear-time codec by Chroni and Nikolopoulos. We extend the work of these authors in various aspects. First, we characterize the class of graphs constituting the image of Chroni and Nikolopoulos's encoding function. Furthermore, we formulate a novel, linear-time watermark-to-key decoding algorithm which detects and recovers from ill-intentioned removals of k ≤ 2 edges. Finally, our results also include the detection of k ≤ 5 edge modifications (insertions/deletions) in polynomial time and a proof that such bound is tight, so the resilience of the considered watermarking scheme is fully determined. Our proof that graphs of a well characterized class can detect—and recover from—bounded-magnitude distortive attacks reinforces the interest in regarding those graphs as possible watermarking solutions to numerous applications.

    @incollection{BBMSS13a,
    	author = {Bento, Lucila Maria de Souza and Boccardo, Davidson and Machado, Raphael Carlos Santos and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o and Szwarcfiter, Jayme Luiz},
    	title = {Towards a provably resilient scheme for graph-based watermarking},
    	booktitle = {Graph-Theoretic Concepts in Computer Science},
    	series = {Lecture Notes in Computer Science},
    	editor = {Brandst\"adt, Andreas and Jansen, Klaus and Reischuk, R\"udiger},
    	publisher = {Springer Berlin Heidelberg},
    	volume = {8165},
    	isbn = {978-3-642-45042-6},
    	pages = {50--63},
    	year = {2013},
    }
            
  6. Polynomial time algorithm for the Radon number of grids in the geodetic convexityPDF DOI slides Abstract BibTeX
    Com Mitre Dourado, Dieter Rautenbach e Jayme Szwarcfiter.
    With Mitre Dourado, Dieter Rautenbach and Jayme Szwarcfiter.
    Anais do the VII Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS'13, Playa del Carmen, México, 22-26/04/13),
    Electronic Notes in Discrete Mathematics 44 (2013), 371-376.
    Proceedings of the VII Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS'13, Playa del Carmen, Mexico, April 22-26, 2013),
    Electronic Notes in Discrete Mathematics 44 (2013), 371-376.

    The Radon number of a graph is the minimum integer r such that all sets of at least r vertices of the graph can be partitioned into two subsets whose convex hulls intersect. We present a near-linear O(d log d) time algorithm to calculate the Radon number of d-dimensional grids in the geodetic convexity. To date, no polynomial time algorithm was known for this problem.

    @inproceedings{DRSS13b,
    	author = {Dourado, Mitre Costa and Rautenbach, Dieter and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o and Szwarcfiter, Jayme Luiz},
    	title = {Polynomial time algorithm for the Radon number of grids in the geodetic convexity},
    	booktitle = {Proceedings of the VII Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS'13)},
    	series = {Electronic Notes in Discrete Mathematics},
    	volume = {44},
    	doi = {10.1016/j.endm.2013.10.058},
    	pages = {371--376},
    	year = {2013},
    }
            
  7. Geodetic number versus hull number in P3 convexityPDF DOI 1-page sample Abstract BibTeX
    Com Carmen Centeno, Lucia Penso e Dieter Rautenbach.
    With Carmen Centeno, Lucia Penso and Dieter Rautenbach.
    SIAM Journal on Discrete Mathematics 27 2 (2013), 717-731.
    SIAM Journal on Discrete Mathematics 27 2 (2013), 717-731.

    We study the graphs G for which the hull number h(G) and the geodetic number g(G) with respect to P3 convexity coincide. These two parameters correspond to the minimum cardinality of a set U of vertices of G such that the simple expansion process that iteratively adds to U, all vertices outside of U that have two neighbors in U, produces the whole vertex set of G either eventually or after one iteration, respectively. We establish numerous structural properties of the graphs G with h(G)=g(G), which allow the constructive characterization as well as the efficient recognition of all triangle-free such graphs. Furthermore, we characterize the graphs G that satisfy h(H)=g(H) for every induced subgraph H of G in terms of forbidden induced subgraphs.

    @article{CPSR2013,
    	author = {Centeno, Carmen Cecilia and Penso, Lucia Draque and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o and Rautenbach, Dieter},
    	title = {Geodetic number versus hull number in $P_3$ convexity},
    	journal = {SIAM Journal on Discrete Mathematics},
    	volume = {27},
    	number = {2},
    	pages = {717--731},
    	year = {2013},
    	issn = {0895-4801},
    	doi = {10.1137/110859014},
    	keywords = {hull number},
    	keywords = {geodetic number},
    	keywords = {$P_3$ convexity},
    	keywords = {irreversible $2$-threshold processes}
    } 
            

            1-page sample

  8. On the geodetic Radon number of gridsPDF DOI slides 1-page sample Abstract BibTeX
    Com Mitre Dourado, Dieter Rautenbach e Jayme Szwarcfiter.
    With Mitre Dourado, Dieter Rautenbach and Jayme Szwarcfiter.
    Discrete Mathematics 313 (2013), 111-121.

    It is NP-hard to determine the Radon number of graphs in the geodetic convexity. However, for certain classes of graphs, this well-known convexity parameter can be determined efficiently. In this paper, we focus on geodetic convexity spaces built upon d-dimensional grids, which are the Cartesian products of d paths. After revisiting a result of Eckhoff concerning the Radon number of Rd in the convexity defined by Manhattan distance, we present a series of theoretical findings that disclose some very nice combinatorial aspects of the problem for grids. We also give closed expressions for the Radon number of the product of P2's and the product of P3's, as well as computer-aided results covering the Radon number of all possible Cartesian products of d paths for d≤ 9.

    @article{DRSS2013a,
        author = {Dourado, Mitre Costa and Rautenbach, Dieter and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o and Szwarcfiter, Jayme Luiz},
        title = {On the geodetic Radon number of grids},
        journal = {Discrete Mathematics},
        volume = {313},
        number = {1},
        pages = {111--121},
        year = {2013},
        issn = {0012-365X},
        doi = {10.1016/j.disc.2012.09.007},
        url = {http://www.sciencedirect.com/science/article/pii/S0012365X12004128},
        keywords = {Radon partition},
        keywords = {Radon number},
        keywords = {Geodetic convexity},
        keywords = {Manhattan distance},
        keywords = {Grid graph},
        keywords = {Cartesian product}
    }
            

            1-page sample

  9. A tight bound for exhaustive key search attacks against message authentication codesPDF DOI 1-page sample Abstract BibTeX
    Com Davidson Boccardo, Luiz Fernando Rust e Raphael Machado.
    With Davidson Boccardo, Luiz Fernando Rust and Raphael Machado.
    RAIRO - Theoretical Informatics and Applications 47 2 (2013), 171-180.

    A message authentication code (MAC) is a function that takes a message and a key as parameters and outputs an authentication of the message. MAC are used to guarantee the legitimacy of messages exchanged through a network, since generating a correct authentication requires the knowledge of the key defined secretly by trusted parties. However, an attacker with access to a sufficiently large number of message/authentication pairs may use a brute force algorithm to infer the secret key: from a set containing initially all possible key candidates, subsequently remove those that yield an incorrect authentication, proceeding this way for each intercepted message/authentication pair until a single key remains. In this paper, we determine an exact formula for the expected number of message/authentication pairs that must be used before such form of attack is successful, along with an asymptotical bound that is both simple and tight. We conclude by illustrating a modern application where this bound comes in handy, namely the estimation of security levels in reflection-based verification of software integrity.

    @article{SBRM2013,
    	author = {Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o and Boccardo, Davidson and Carmo, Luiz Fernando Rust da Costa and Machado, Raphael Carlos Santos},
    	title = {A tight bound for exhaustive key search attacks against Message Authentication Codes},
    	journal = {RAIRO - Theoretical Informatics and Applications},
    	volume = {47},
    	issue = {2},
    	pages = {171--180},
    	year = {2013},
    	issn = {1290-385X},
    	doi = {10.1051/ita/2012025},
    	url = {http://www.rairo-ita.org/action/article_S0988375412000252},
    }
            

            1-page sample

Voltar ao topo

Back to top

2012

  1. Geodetic number versus hull number in P3 convexityPDF Abstract BibTeX
    Com Carmen Centeno, Lucia Penso e Dieter Rautenbach.
    With Carmen Centeno, Lucia Penso and Dieter Rautenbach.
    Livro de Abstracts do 5th Latin-American Workshop on Cliques in Graphs (LAWCG'12, Buenos Aires, Argentina, 05-07/11/12).
    Book of Abstracts of the 5th Latin-American Workshop on Cliques in Graphs (LAWCG'12, Buenos Aires, Argentina, November 05-07, 2012).

    We study the graphs G for which the hull number h(G) and the geodetic number g(G) with respect to P3 convexity coincide. These two parameters correspond to the minimum cardinality of a set U of vertices of G such that the simple expansion process that iteratively adds to U, all vertices outside of U that have two neighbors in U, produces the whole vertex set of G either eventually or after one iteration, respectively. We establish numerous structural properties of the graphs G with h(G)=g(G), which allow the constructive characterization as well as the efficient recognition of all triangle-free such graphs. Furthermore, we characterize the graphs G that satisfy h(H)=g(H) for every induced subgraph H of G in terms of forbidden induced subgraphs.

    @inproceedings{CPRS12,
    	author = {Centeno, Carmen Cecilia and Penso, Lucia Draque and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o and Rautenbach, Dieter},
    	title = {Geodetic number versus hull number in $P_3$ convexity},
    	booktitle = {Book of Abstracts of the 5th Latin-American Workshop on Cliques in Graphs (LAWCG'12)},
    	year = {2012},
    }
            
  2. Hashing na solução de problemas atípicosPDF Abstract BibTeX
    Com Lucila Bento e Jayme Szwarcfiter.
    With Lucila Bento and Jayme Szwarcfiter.
    Anais do XVI Congreso Latino-Iberoamericano de Investigación Operativa / XLIV Simpósio Brasileiro de Pesquisa Operacional (CLAIO/SBPO'12, Rio de Janeiro/RJ, Brasil, 24-28/09/12), 3280-3290.
    Proceedings of the XVI Congreso Latino-Iberoamericano de Investigación Operativa / XLIV Simpósio Brasileiro de Pesquisa Operacional (CLAIO/SBPO'12, Rio de Janeiro/RJ, Brazil, September 24-28, 2012), 3280-3290.

    A organização de dados em tabelas de dispersão é uma técnica bastante difundida, onde os valores a serem persistidos estão relacionados a chaves de busca usadas para o cálculo dos endereços de seu armazenamento. Por proverem bom desempenho nas chamadas operaçães de dicionário (inserção, busca e remoção) sem requerer espaço exorbitante, as tabelas de dispersão são empregadas frequentemente na indexação de grandes volumes de dados e em aplicaçães típicas relacionadas à associação, busca e manipulação da informação. No entanto, há problemas que, mesmo possuindo natureza bem diversa, podem ser solucionados de maneira elegante com o emprego de tabelas de dispersão, resultando em sensível economia de tempo e espaço. Este artigo ilustra o poder dessa técnica, também chamada hashing, em situaçães que não lhe são comumente associadas.

    The organization of data into hash tables is a well-known technique in which the persistent values correspond to search keys upon which their storage addresses are calculated. Since they provide good performance for the so-called dictionary operations (insertion, lookup, deletion) without requiring exorbitant space, hash tables are very often employed in the indexation of large amounts of data and in typical applications related to search and handling of information. Nevertheless, there are problems of rather different nature that can be solved in elegant fashion by employing hash tables, yielding significant economy of time and space. This paper illustrates the power of such technique in situations it is not usually associated to.

    @inproceedings{BSS12b,
    	author = {Bento, Lucila Maria de Souza and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o and Szwarcfiter, Jayme Luiz},
    	title = {Hashing na solu{\c c}{\~a}o de problemas at{\'i}picos},
    	booktitle = {Anais do XVI Congreso Latino-Iberoamericano de Investigaci{\'o}n Operativa / XLIV Simp{\'o}sio Brasileiro de Pesquisa Operacional (CLAIO/SBPO'12)},
    	pages = {3280--3290},
    	url = {http://www2.claiosbpo2012.iltc.br/pdf/101042.pdf},
    	year = {2012},
    }
            
  3. Hashing na solução de problemas combinatórios difíceisPDF poster Abstract BibTeX
    Com Lucila Bento e Jayme Szwarcfiter.
    With Lucila Bento and Jayme Szwarcfiter.
    Anais do XXXIV Congresso Nacional de Matemática Aplicada e Computacional (CNMAC'12, Águas de Lindóia/SP, Brasil, 17-21/09/12).
    Proceedings of the XXXIV Congresso Nacional de Matemática Aplicada e Computacional (CNMAC'12, Águas de Lindóia/SP, Brazil, September 17-21, 2012).

    Problemas de otimização combinatória possuem grande importância prática, aparecendo em diversas aplicações. Muitos são difíceis de se resolver, pois requerem a busca de uma solução num espaço exponencialmente grande, sem que algoritmos e ficientes sejam conhecidos, ou mesmo possíveis. Neste trabalho, é apresentada uma técnica que, utilizando hashing como coadjuvante à busca exaustiva (backtracking), oferece ganhos consideráveis de tempo e espaço em muitas situações. Os problemas Carga da Balsa e Quebra-cabeça do 15 serão abordados para ilustrar seu uso.

    @inproceedings{BSS12a,
    	author = {Bento, Lucila Maria de Souza and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o and Szwarcfiter, Jayme Luiz},
    	title = {Hashing na solu{\c c}{\~a}o de problemas combinat{\'o}rios dif{\'i}ceis},
    	booktitle = {Anais do XXXIV Congresso Nacional de Matem{\'a}tica Aplicada e Computacional (CNMAC'12)},
    	year = {2012},
    }
            
  4. Linear time approximations for dominating sets and independent dominating sets in unit disk graphsPDF DOI slides Abstract BibTeX
    Com Guilherme Fonseca, Celina Figueiredo e Raphael Machado.
    With Guilherme Fonseca, Celina Figueiredo and Raphael Machado.
    Anais do 10th Workshop on Approximation and Online Algorithms (WAOA'12, Ljubljana, Eslovênia, 13-14/09/12),
    Lecture Notes in Computer Science 7846 (2013), 82-92.
    Proceedings of the 10th Workshop on Approximation and Online Algorithms (WAOA'12, Ljubljana, Slovenia, September 13-14, 2012),
    Lecture Notes in Computer Science 7846 (2013), 82-92.

    A unit disk graph is the intersection graph of n congruent disks in the plane. Dominating sets in unit disk graphs are widely studied due to their application in wireless ad-hoc networks. Since the minimum dominating set problem for unit disk graphs is NP-hard, several approximation algorithms with different merits have been proposed in the literature. On one extreme, there is a linear time 5-approximation algorithm. On another extreme, there are two PTAS whose running times are polynomials of very high degree. We introduce a linear time approximation algorithm that takes the usual adjacency representation of the graph as input and attains a 44/9 approximation factor. This approximation factor is also attained by a second algorithm we present, which takes the geometric representation of the graph as input and runs in O(n log n) time, regardless of the number of edges. The analysis of the approximation factor of the algorithms, both of which are based on local improvements, exploits an assortment of results from discrete geometry to prove that certain graphs cannot be unit disk graphs. It is noteworthy that the dominating sets obtained by our algorithms are also independent sets.

    @incollection{FSMF12,
    	author = {da Fonseca, Guilherme Dias and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o and Machado, Raphael Carlos Santos and de Figueiredo, Celina Miraglia Herrera},
    	title = {Linear time approximations for dominating sets and independent dominating sets in unit disk graphs},
    	booktitle = {Approximation and Online Algorithms},
    	editor = {Erlebach, Thomas and Persiano, Giuseppe},
    	publisher = {Springer Berlin Heidelberg},
    	series = {Lecture Notes in Computer Science},
    	volume = {7846},
    	isbn = {978-3-642-38015-0},
    	doi = {10.1007/978-3-642-38016-7_8},
    	pages = {82--92},
    	year = {2013},
    }
            
  5. Immediate versus eventual conversion: comparing geodetic and hull numbers in P3 convexityPDF DOI slides Abstract BibTeX
    Com Carmen Centeno, Lucia Penso e Dieter Rautenbach.
    With Carmen Centeno, Lucia Penso and Dieter Rautenbach.
    Anais do 38th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'12, Jerusalém, Israel, 26-28/06/12),
    Lecture Notes in Computer Science 7551 (2012), 262-273.
    Proceedings of the 38th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'12, Jerusalem, Israel, June 26-28, 2012),
    Lecture Notes in Computer Science 7551 (2012), 262-273.

    We study the graphs G for which the hull number h(G) and the geodetic number g(G) with respect to P3 convexity coincide. These two parameters correspond to the minimum cardinality of a set U of vertices of G such that the simple expansion process that iteratively adds to U, all vertices outside of U that have two neighbors in U, produces the whole vertex set of G either eventually or after one iteration, respectively. We establish numerous structural properties of the graphs G with h(G) = g(G), which allow the constructive characterization as well as the efficient recognition of all triangle-free such graphs. Furthermore, we characterize the graphs G that satisfy h(H) = g(H) for every induced subgraph H of G in terms of forbidden induced subgraphs.

    @incollection{CPRS12,
    	author = {Centeno, Carmen Cecilia and Penso, Lucia Draque and Rautenbach, Dieter and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o},
    	title = {Immediate versus eventual conversion: comparing geodetic and hull numbers in P3 convexity},
    	booktitle = {Graph-Theoretic Concepts in Computer Science},
    	editor = {Golumbic, Martin Charles and Stern, Michal and Levy, Avivit and Morgenstern, Gila},
    	series = {Lecture Notes in Computer Science},
    	publisher = {Springer Berlin Heidelberg},
    	volume = {7551},
    	pages = {262--273},
    	isbn = {978-3-642-34610-1},
    	doi = {10.1007/978-3-642-34611-8_27},
    	year = {2012},
    }
            

Voltar ao topo

Back to top

Older

+Antigos

  1. Complexity dichotomy on partial grid recognitionPDF DOI arXiv slides 1-page sample Abstract BibTeX
    Com Celina Figueiredo, Guilherme Fonseca e Raphael Machado.
    With Celina Figueiredo, Guilherme Fonseca and Raphael Machado.
    Theoretical Computer Science 412 (2011), 2370-2379.

    Deciding whether a graph can be embedded in a grid using only unit-length edges is NP-complete, even when restricted to binary trees. However, it is not difficult to devise a number of graph classes for which the problem is polynomial, even trivial. A natural step, outstanding thus far, was to provide a broad classification of graphs that make for polynomial or NP-complete instances. We provide such a classification based on the set of allowed vertex degrees in the input graphs, yielding a full dichotomy on the complexity of the problem. As byproducts, the previous NP-completeness result for binary trees was strengthened to strictly binary trees, and the three-dimensional version of the problem was for the first time proven to be NP-complete. Our results were made possible by introducing the concepts of consistent orientations and robust gadgets, and by showing how the former allows NP-completeness proofs by local replacement even in the absence of the latter.

    @article{SFMF2011,
    	author = {Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o and da Fonseca, Guilherme Dias and Machado, Raphael Carlos Santos and de Figueiredo, Celina Miraglia Herrera},
    	title = {Complexity dichotomy on partial grid recognition},
    	journal = {Theoretical Computer Science},
    	volume = {412},
    	issue = {22},
    	pages = {2370--2379},
    	year = {2011},
    	issn = {0304-3975},
    	doi = {10.1016/j.tcs.2011.01.018},
    	keywords = {Graph embedding},
    	keywords = {VLSI layout},
    	keywords = {Partial grid},
    	keywords = {NP-completeness}
    } 
            

            1-page sample

  2. Complexity dichotomy on degree-constrained VLSI layouts with unit-length edgesPDF DOI slides Abstract BibTeX
    Com Celina Figueiredo, Guilherme Fonseca e Raphael Machado.
    With Celina Figueiredo, Guilherme Fonseca and Raphael Machado.
    Anais do International Symposium on Combinatorial Optimization (ISCO'10, Hammamet, Tunísia, 24-26/03/10),
    Electronic Notes in Discrete Mathematics 36 (2010), 391-398.
    Proceedings of the International Symposium on Combinatorial Optimization (ISCO'10, Hammamet, Tunisia, March 24-26, 2010),
    Electronic Notes in Discrete Mathematics 36 (2010), 391-398.

    Deciding whether an arbitrary graph admits a VLSI layout with unit-length edges is NP-complete, even when restricted to binary trees. However, for certain graphs, the problem is polynomial or even trivial. A natural step, outstanding thus far, was to provide a broader classification of graphs that make for polynomial or NP-complete instances. We provide such a classification based on the set of vertex degrees in the input graphs, yielding a comprehensive dichotomy on the complexity of the problem, with and without the restriction to trees.

    @incollection{SFFM10,
    	author = {Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o and de Figueiredo, Celina Miraglia Herrera and da Fonseca, Guilherme Dias and Machado, Raphael Carlos Santos},
    	title = {Complexity dichotomy on degree-cconstrained VLSI layouts with unit-length edges},
    	booktitle = {Proceedings of the International Symposium on Combinatorial Optimization (ISCO'10)},
    	series = {Electronic Notes in Discrete Mathematics},
    	volume = {36},
    	pages = {391--398},
    	issn = {1571-0653},
    	doi = {10.1016/j.endm.2010.05.050},
    	year = {2010},
    }
            
  3. Duas vezes cem é igual a duzentos?  PDF BibTeX
    Com Ilydio Pereira de Sá.
    With Ilydio Pereira de Sá.
    Revista do Professor de Matemática 70 (2009), 13-16.
    @article{SS09,
    	author = {Pereira de S{\'a}, Ilydio and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o},
    	title = {Duas vezes 100 {\'e} igual a 200?},
    	journal = {Revista do Professor de Matemática},
    	volume = {70},
    	pages = {13--16},
    	year = {2009},
    	issn = {0102-4981},
    }
            
  4. Desafio: a Porta dos Desesperados (parte 2)PDF BibTeX
    Com Ilydio Pereira de Sá.
    With Ilydio Pereira de Sá.
    Boletim GEPEM 52 (2008), 105-107.
    @article{SS08,
    	author = {Pereira de S{\'a}, Ilydio and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o},
    	title = {Desafio: a Porta dos Desesperados (parte 2)},
    	journal = {Boletim GEPEM},
    	volume = {52},
    	pages = {105--107},
    	year = {2008},
    	issn = {0104-9739},
    }
            
  5. Desafio: a Porta dos Desesperados (parte 1)PDF BibTeX
    Com Ilydio Pereira de Sá.
    With Ilydio Pereira de Sá.
    Boletim GEPEM 51 (2007), 102-103.
    @article{SS07,
    	author = {Pereira de S{\'a}, Ilydio and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o},
    	title = {Desafio: a Porta dos Desesperados (parte 1)},
    	journal = {Boletim GEPEM},
    	volume = {51},
    	pages = {102--103},
    	year = {2007},
    	issn = {0104-9739},
    }
            
  6. Introdução aos Algoritmos RandomizadosPDF slides BibTeX
    Com Celina Figueiredo, Guilherme Fonseca e Manoel Lemos.
    With Celina Figueiredo, Guilherme Fonseca and Manoel Lemos.
    Livro publicado por ocasião do 26° Colóquio Brasileiro de Matemática.
    IMPA, Rio de Janeiro, 2007.
    Book published for the 26th Colóquio Brasileiro de Matemática.
    IMPA, Rio de Janeiro, 2007.
    @book{FFLS07,
    	author = {de Figueiredo, Celina Miraglia Herrera and da Fonseca, Guilherme Dias and Lemos, Manoel Jos{\'e} Machado Soares and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o},
    	title =  {Introdu{\c c}{\~a}o aos Algoritmos Randomizados},
    	publisher = {Instituto Nacional de Matem{\'a}tica Pura e Aplicada},
    	year = {2007},
    }
            
  7. Ten algorithms for the homogeneous set sandwich problemPDF Abstract BibTeX
    Anais do XXVII Congresso da Sociedade Brasileira de Computação (CSBC'07, Rio de Janeiro/RJ, Brasil, 03-04/07/07), 1958-1965.
    Proceedings of the XXVII Congresso da Sociedade Brasileira de Computação (CSBC'07, Rio de Janeiro/RJ, Brazil, July 03-04, 2007), 1958-1965.

    Sandwich problems are generalizations of graph recognition problems where the input instance is provided with a set of optional edges. Originally arisen from Computational Biology applications, they have long encompassed other research areas. Many sandwich problems considered in the literature have been found to be NP-complete. Among those which are polynomial, the most interesting—from the standpoint of algorithm development and analysis—are those which have not yet been as efficiently solved as their non-sandwich counterparts. To this latter group belongs the Homogeneous Set Sandwich Problem, the subject of this thesis. After the two first algorithms (not ours) published for the HSSP, the most recent of which proven incorrect by the author, there followed a sequence of six faster algorithms (ours) in a continuous refinement of ideas and techniques, culminating at the establishment of the problem's currently accepted upper bound. We introduce as well two efficient—and quite didactic, as experience has shown—randomized algorithms for the problem.

    @inproceedings{S07,
    	author = {Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o},
    	title = {Ten algorithms for the homogeneous set sandwich problem},
    	booktitle = {Anais do XXVII Congresso da Sociedade Brasileira de Computa{\c c}{\~a}o (CSBC'07)},
    	pages = {1958--1965},
    	year = {2007},
    }
            
  8. The Growing Cliques algorithm for the homogeneous set sandwich problemPDF Abstract BibTeX
    Com Celina Figueiredo e Guilherme Fonseca.
    With Celina Figueiredo e Guilherme Fonseca.
    Livro de Abstracts do 2nd Latin-American Workshop on Cliques in Graphs (LAWCG'06, La Plata, Argentina, 18-20/10/06).
    Book of Abstracts of the 2nd Latin-American Workshop on Cliques in Graphs (LAWCG'06, La Plata, Argentina, October 18-20, 2006).

    A homogeneous set is a non-trivial module of a graph, i.e. a non-empty, non-unitary, proper subset of a graphs vertices such that all its elements present exactly the same outer neighborhood. Given two graphs G1(V,E1), G2(V,E2), the Homogeneous Set Sandwich Problem (HSSP) asks whether there exists a sandwich graph GS(V,ES), E1ES⊆ E2, which has a homogeneous set. In 2001, Tang et al. published an all-fast O(n2Δ2) algorithm which was afterwards proven wrong, so that the HSSP's known upper bound would have been reset at former O(n4) determined by Cerioli et al. in 1998. However, an O(n3.5) algorithm, based on the balancing technique, and an O(n3) randomized Monte Carlo algorithm were devised shortly thereafter. We present the concept of enemy vertices, which establishes a relationship between sandwich homogeneous sets and independent sets. It is the underlying principle of the approach in which clique covers are employed to bound the size of the maximum independent set in an auxiliary graph, therefore imposing the best possible upper bound to the size of sandwich homogeneous sets we shall search for at each iteration of a new O(n3 log n) deterministic algorithm.

    @inproceedings{FFS06,
    	author = {da Fonseca, Guilherme Dias and de Figueiredo, Celina Miraglia Herrera and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o},
    	title = {The Growing Cliques algorithm for the homogeneous set sandwich problem},
    	booktitle = {Book of Abstracts of the 2nd Latin-American Workshop on Cliques in Graphs (LAWCG'06)},
    	year = {2006},
    }
            
  9. The pair completion algorithm for the homogeneous set sandwich problemPDF DOI 1-page sample Abstract BibTeX
    Com Claudson Bornstein e Celina Figueiredo.
    With Claudson Bornstein and Celina Figueiredo.
    Information Processing Letters 98 (2006), 87-91.

    A homogeneous set is a non-trivial module of a graph, i.e.  a non-empty, non-unitary, proper vertex subset such that all its elements present the same outer neighborhood. Given two graphs G1(V,E1) and G2(V,E2), the Homogeneous Set Sandwich Problem asks whether there exists a graph GS(V,ES), E1ESE2, which has a homogeneous set. This paper presents an algorithm that uses the concept of bias graph to solve the problem in O(n min{|E1|, |E2|} log n) time, thus outperforming the other known HSSP deterministic algorithms for inputs where max{|E1|, |E2|} = Ω(n log n).

    @article{BFS06,
    	author = {Bornstein, Claudson Ferreira and de Figueiredo, Celina Miraglia Herrera and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o},
    	title = {The pair completion algorithm for the homogeneous set sandwich problem},
    	journal = {Information Processing Letters},
    	doi = {10.1016/j.ipl.2005.12.010},
    	pages = {87--91},
    	volume = {98},
    	year = {2006},
    }
            

            1-page sample

  10. Algorithms for the homogeneous set sandwich problemPDF DOI 1-page sample Abstract BibTeX
    Com Celina Figueiredo, Guilherme Fonseca e Jeremy Spinrad.
    With Celina Figueiredo, Guilherme Fonseca and Jeremy Spinrad.
    Algorithmica 46 2 (2006), 149-180.

    A homogeneous set is a non-trivial module of a graph, i.e.  a non-empty, non-unitary, proper subset of a graph's vertices such that all its elements present exactly the same outer neighborhood. Given two graphs G1(V,E1), G2(V,E2), the Homogeneous Set Sandwich Problem asks whether there exists a sandwich graph GS(V,ES), E1ESE2, which has a homogeneous set. In 2001, Tang et al. published an all-fast O(n2 Δ2) algorithm which was recently proven wrong, so that the HSSP's known upper bound would have been reset thereafter at former O(n4) determined by Cerioli et al. in 1998. We present, notwithstanding, new deterministic algorithms which have it established at O(n3 log m/n). We give as well two even faster O(n3) randomized algorithms, whose simplicity might lend them didactic usefulness. We believe that, besides providing efficient easy-to-implement procedures to solve it, the study of these new approaches allows a fairly thorough understanding of the problem.

    @article{FFSS06,
    	author = {de Figueiredo, Celina Miraglia Herrera and da Fonseca, Guilherme Dias and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o and Spinrad, J.},
    	title = {Algorithms for the homogeneous set sandwich problem},
    	journal = {Algorithmica},
    	doi = {10.1007/s00453-005-1198-2},
    	issn = {0178-4617},
    	issue = {2},
    	pages = {149--180},
    	volume = {46},
    	year = {2006},
    }
            

            1-page sample

  11. Dez algoritmos para o problema-sanduíche do conjunto homogêneoPDF Abstract BibTeX
    Tese de doutorado.
    D.Sc. thesis.
    COPPE, Universidade Federal do Rio de Janeiro, 2006.
    Awardee of the 2nd prize of the Dissertations and Theses Contest sponsored by the Brazilian Computing Society in 2007.
    Awardee of the Honorable Mention of the CAPES Theses Award in the same year.
    Recebedora do 2º prêmio do Concurso de Teses e Dissertações promovido pela Sociedade Brasileira de Computação em 2007.
    Recebedora da Menção Honrosa do Prêmio CAPES de Teses naquele mesmo ano.

    Problemas-sanduíche são generalizações de problemas de reconhecimento em grafos, onde ao grafo de entrada — no qual investiga-se a existência de determinada propriedade — é oferecido um conjunto de arestas opcionais. Esta classe de problemas foi originalmente formulada com vistas a aplicaçães práticas em Biologia Computacional, mas sua abrangência já há muito não se encontra limitada àquele campo de pesquisa. Muitos dos problemas-sanduíche abordados na literatura até este momento mostraram-se NP-completos. Dentre aqueles polinomiais, os mais interessantes — do ponto de vista da criação e análise de algoritmos — são os que não se sabe ainda resolver com eficiência semelhante à que se consegue para os problemas de reconhecimento clássicos que lhes são correspondentes. Pertence a este grupo o Problema-Sanduíche do Conjunto Homogêneo, tema desta tese, e para o qual apresentamos dez algoritmos distintos (oito de nossa autoria).

    Sandwich problems are generalizations of graph recognition problems, where the input instance graph—which will be investigated as for the existence of a certain property—is provided with a set of optional edges. This class of problems originally arose due to some Computational Biology practical applications, but it has long encompassed other research fields. Many sandwich problems considered in the literature have been found to be NP-complete. Among those which are polynomial, the most interesting—from the standpoint of algorithm development and analysis—are those which are not yet solvable with an efficiency close to that achieved for their counterpart classical recognition problems. To this latter group belongs the Homogeneous Set Sandwich Problem, the subject of this thesis, and for which we present ten distinct algorithms (eight of them authored by us). We believe that the text allows not only a thorough understanding of the problem and its singularities, but also provides the reader with a broad—and quite didactic—portrayal of the more general process of creation and refinement of techniques, in the constant search for the optimum algorithm.

    @phdthesis{S06,
    	author = {Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o},
    	title =  {Dez algoritmos para o problema-sandu{\'i}che do conjunto homog{\^e}neo},
    	school = {COPPE, Universidade Federal do Rio de Janeiro},
    	supervisor = {Celina Miraglia Herrera de Figueiredo},
    	year = {2006},
    }
            
  12. Note on the homogeneous set sandwich problemPDF DOI 1-page sample Abstract BibTeX
    Com Celina Figueiredo.
    With Celina Figueiredo.
    Information Processing Letters 93 (2005), 75-81.

    A homogeneous set is a non-trivial module of a graph, i.e.  a non-unitary, proper subset H of a graph's vertices such that all vertices in H have the same neighbors outside H. Given two graphs G1(V,E1), G2(V,E2), the Homogeneous Set Sandwich Problem asks whether there exists a sandwich graph GS(V,ES), E1ESE2, which has a homogeneous set. Recently, Tang et al. proposed an interesting O(Δ1 n2) algorithm for this problem, which has been considered its most efficient algorithm since. We show the incorrectness of their algorithm by presenting three counterexamples.

    @article{FS05,
    	author = {de Figueiredo, Celina Miraglia Herrera and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o},
    	title = {Note on the homogeneous set sandwich problem},
    	journal = {Information Processing Letters},
    	doi = {10.1016/j.ipl.2004.09.022},
    	pages = {75--81},
    	volume = {93},
    	year = {2005},
    }
            

            1-page sample

  13. The homogeneous set sandwich problemPDF Abstract BibTeX
    Anais do XXIV Congresso da Sociedade Brasileira de Computação (CSBC'04, Salvador/BA, Brasil, 04-05/08/04).
    Proceedings of the XXIV Congresso da Sociedade Brasileira de Computação (CSBC'04, Salvador/BA, Brazil, August 04-05, 2004).

    Homogeneous sets have proved useful for the construction of graph decomposition procedures. Sandwich graphs are obtained from two pre-defined graphs which provide them with both mandatory and optional edges. Given such a pair of graphs, the Homogeneous Set Sandwich Problem (HSSP) searches for a sandwich graph which contains a homogeneous set. This thesis presents the development of techniques for solving the HSSP and culminates in the correction of the established upper bounds for its time complexity. Such results comprise the description of thoroughly depicted counterexamples which prove the incorrectness of the (so far) best published HSSP algorithm, along with the proposal of a new, faster algorithm.

    @inproceedings{S04,
    	author = {Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o},
    	title = {The homogeneous set sandwich problem},
    	booktitle = {Anais do XXIV Congresso da Sociedade Brasileira de Computa{\c c}{\~a}o (CSBC'04)},
    	year = {2004},
    }
            
  14. Faster deterministic and randomized algorithms on the homogeneous set sandwich problemPDF DOI Abstract BibTeX
    Com Celina Figueiredo, Guilherme Fonseca e Jeremy Spinrad.
    With Celina Figueiredo, Guilherme Fonseca and Jeremy Spinrad.
    Anais do III Workshop on Efficient and Experimental Algorithms (WEA'04, Angra dos Reis/RJ, Brasil, 25-28/05/04),
    Lecture Notes in Computer Science 3058 (2004), 243-252.
    Proceedings of the III Workshop on Experimental and Efficient Algorithms (WEA'04, Angra dos Reis/RJ, Brazil, May 25-28, 2004),
    Lecture Notes in Computer Science 3058 (2004), 243-252.

    A homogeneous set is a non-trivial, proper subset of a graph's vertices such that all its elements present exactly the same outer neighborhood. Given two graphs, G1(V,E1), G2(V,E2), we consider the problem of finding a sandwich graph GS(V,ES), with E1ESE2, which contains a homogeneous set, in case such a graph exists. This is called the Homogeneous Set Sandwich Problem (HSSP). We give an O(n3.5) deterministic algorithm, which updates the known upper bounds for this problem, and an O(n3) Monte Carlo algorithm as well. Both algorithms, which share the same underlying idea, are quite easy to be implemented on the computer.

    @incollection{FFSS04,
    	author = {de Figueiredo, Celina Miraglia Herrera and da Fonseca, Guilherme Dias and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o and Spinrad, Jeremy},
    	title = {Faster deterministic and randomized algorithms on the homogeneous set sandwich problem},
    	series = {Lecture Notes in Computer Science},
    	booktitle = {Experimental and Efficient Algorithms},
    	publisher = {Springer Berlin Heidelberg},
    	editor = {Ribeiro, Celso C. and Martins, Simone L.},
    	pages = {243--252},
    	isbn = {978-3-540-22067-1},
    	doi = {10.1007/978-3-540-24838-5_18},
    	year = {2004},
    }
            
  15. A fast Monte Carlo algorithm for the homogeneous set sandwich problemPDF slides Abstract BibTeX
    Com Celina Figueiredo e Guilherme Fonseca.
    With Celina Figueiredo e Guilherme Fonseca.
    Anais do Mathematical Programming in Rio: a Conference in Honour of Nelson Maculan (MPinRio'03, Armação dos Búzios/RJ, Brasil, 09-12/11/03), 35-39.
    Proceedings of Mathematical Programming in Rio: a Conference in Honour of Nelson Maculan (MPinRio'03, Armação dos Búzios/RJ, Brazil, November 09-12, 2003), 35-39.

    A homogeneous set is a non-trivial, proper subset of a graph's vertices such that all its elements present exactly the same outer neighborhood. Given two graphs, G1(V,E1), G2(V,E2), we consider the problem of finding a sandwich graph GS(V,ES), E1ESE2, which contains a homogeneous set, in case such a graph exists. This is called the Homogeneous Set Sandwich Problem (HSSP). We give a simple O(n3) Monte Carlo algorithm which is asymptotically more efficient than all deterministic HSSP algorithms known so far.

    @inproceedings{FFS03,
    	author = {de Figueiredo, Celina Miraglia Herrera and da Fonseca, Guilherme Dias and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o},
    	title = {A fast Monte Carlo algorithm for the homogeneous set sandwich problem},
    	booktitle = {Proceedings of Mathematical Programming in Rio: a Conference in Honor of Nelson Maculan},
    	pages = {35--39},
    	year = {2003},
    }
            
  16. A new upper bound for the homogeneous set sandwich problemPDF Abstract BibTeX
    Com Celina Figueiredo.
    With Celina Figueiredo.
    Anais do Workshop on Combinatorics, Algorithms and Applications (WCAA'03, Ubatuba/SP, Brasil, 01-05/09/03).
    Proceedings of the Workshop on Combinatorics, Algorithms and Applications (WCAA'03, Ubatuba/SP, Brazil, September 01-05, 2003).

    A homogeneous set is a non-trivial module of a graph, i.e.  a non-empty, non-unitary, proper subset H of a graph's vertices such that all vertices in H have the same neighbors outside H.. Given two graphs G1(V,E1), G2(V,E2), the Homogeneous Set Sandwich Problem asks whether there exists a sandwich graph GS(V,ES), E1ESE2, which has a homogeneous set. Two years ago, Tang et al. proposed an interesting O(Δ1 n2) algorithm for this problem, which has been considered its most efficient algorithm since. We show the incorrectness of their algorithm and present a new deterministic algorithm for the Homogeneous Set Sandwich Problem, whose O(m1 m'2) time complexity becomes its current upper bound.

    @inproceedings{FS03,
    	author = {de Figueiredo, Celina Miraglia Herrera and Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o},
    	title = {A new upper bound for the homogeneous set sandwich problem},
    	booktitle = {Proceedings of the Workshop on Combinatorics, Algorithms and Applications (WCAA'03)},
    	year = {2003},
    }
            
  17. O problema-sanduíche para conjuntos homogêneos em grafosPDF Abstract BibTeX
    Dissertação de mestrado.
    M.Sc. dissertation.
    COPPE, Universidade Federal do Rio de Janeiro, 2003.
    Awardee of the 2nd prize of the Dissertations and Theses Contest sponsored by the Brazilian Computing Society in 2004.
    Recebedora do 2º prêmio do Concurso de Teses e Dissertações promovido pela Sociedade Brasileira de Computação em 2004.

    O conceito de conjunto homogêneo é de grande valia para a elaboração de procedimentos de decomposição de grafos. Grafos-sanduíche são obtidos a partir de dois grafos pré-definidos que lhes emprestam arestas, entre obrigatórias e opcionais. No Problema-Sanduíche para Conjuntos Homogêneos (PSCH), deseja-se descobrir se há, para um par de grafos dado, um grafo-sanduíche que possua algum conjunto homogêneo. Não obstante haver algoritmos lineares para a determinação de conjuntos homogêneos em um grafo isolado, o PSCH continua a ser objeto de pesquisa, dadas as atuais complexidades dos algoritmos existentes e a importância crescente das modelagens grafo-sanduíche para inúmeras aplicaçães práticas. Este trabalho reúne a evolução das técnicas de resolução deste problema e os esforços do autor no sentido de solucioná-lo eficientemente, culminando na correção do limite superior até então aceito para sua complexidade temporal.

    The concept of homogeneous sets has proved itself useful for the construction of graph decomposition procedures. Sandwich graphs are obtained from two pre-defined graphs that provide them with both mandatory and optional edges. In the Homogeneous Set Sandwich Problem (HSSP), one wants to find out whether there exists an instance of a sandwich graph, for a given pair of graphs, which contains some homogeneous set. Notwithstanding the existence of linear-time algorithms for solving the problem of finding homogeneous sets in a single graph, the HSSP still remains a subject for research, not only because of the rather high time complexities of current algorithms but also motivated by the increasing importance of sandwich-graph modelling to many practical applications. This thesis presents the development of techniques for solving this problem, as well as the author’s efforts to find a more efficient solution to it, which culminate in the correction of the established upper bounds for its time complexity.

    @mastersthesis{S03,
    	author = {Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o},
    	title =  {O problema-sandu{\'i}che para conjuntos homog{\^e}neos em grafos},
    	school = {COPPE, Universidade Federal do Rio de Janeiro},
    	supervisor = {Celina Miraglia Herrera de Figueiredo},
    	year = {2003},
    }
            
  18. Ciclos de suporte para anéis virtuais em grafos & Goonie: uma ferramenta para visualização e manipulação de grafosBibTeX
    Monografia (Projeto Final de Curso).
    B.Sc. monograph.
    Instituto de Matemática, Universidade Federal do Rio de Janeiro, 2001.
    @mastersthesis{S01,
        type = {Bachelor's Thesis},
    	author = {Pereira de S{\'a}, Vin{\'i}cius Gusm{\~a}o},
    	title = {Ciclos de suporte para an{\'e}is virtuais em grafos \&
    			 Goonie: uma ferramenta para visualiza{\c c}{\~a}o e manipula{\c c}{\~a}o de grafos},
    	school = {Instituto de Matem{\'a}tica, Universidade Federal do Rio de Janeiro},
    	supervisor = {Nelson Maculan Filho},
    	year = {2001},
    }
            

Voltar ao topo

Back to top