Main page
2019
2018
2017
2016
2015
2014
2013
2012
Older
Página principal
2019
2018
2017
2016
2015
2014
2013
2012
+Antigos
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 graphs 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, which we call canonical reducible permutation graphs. A linear-time recognition algorithm is also given, setting the basis for a polynomial-time algorithm to restore watermarks that underwent the malicious removal of some edges. Finally, we give a simpler decoding algorithm for Chroni and Nikolopoulos' watermarks.
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.
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.
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.
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.
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.
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.
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}
}
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.
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.
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.
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.
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}
}
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.
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}
}
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},
}
Um grafo de fluxo redutível G = (V, E, s) é um grafo direcionado com uma fonte s ∈ V(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},
}
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.
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.
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}
}
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},
}
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},
}
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.
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).
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}
}
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}
}
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},
}
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 ≤ n ≤ 430,
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},
}
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},
}
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},
}
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},
}
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},
}
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}
}
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}
}
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},
}
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},
}
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},
}
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},
}
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},
}
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},
}
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}
}
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},
}
@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},
}
@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},
}
@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},
}
@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},
}
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},
}
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), E1 ⊆ ES⊆ 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},
}
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), E1⊆ES⊆E2, 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},
}
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), E1⊆ES⊆E2, 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},
}
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},
}
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), E1 ⊆ ES ⊆ E2, 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},
}
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},
}
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 E1⊆ES⊆E2, 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},
}
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), E1 ⊆ ES ⊆ E2, 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},
}
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), E1⊆ES⊆E2, 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},
}
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 authors
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},
}
@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},
}