BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Raphael C. S. Machado

Raphael C. S. Machado appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Discrete Mathematicsmath.COComputational ComplexityCryptography and SecurityData Structures and AlgorithmsMultimedia

Catalog footprint

What is connected

5works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

5 published item(s)

preprint2016arXiv

Dijkstra Graphs

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, describe an algorithm to decide whether or not it is structured, that is, whether it conforms to the stated principles of structured programming. We refer to the classical concept of structured programming, as described by Dijkstra. By employing a graph model and graph-theoretic techniques, 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 a greedy $O(n)$-time algorithm. Furthermore, we describe an isomorphism algorithm for Dijkstra graphs, whose complexity is also linear in the number of vertices of the graph. Both the recognition and isomorphism algorithms have potential important applications, such as in code similarity analysis.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Towards a provably resilient scheme for graph-based watermarking

Digital watermarks have been considered a promising way to fight software piracy. Graph-based watermarking schemes encode authorship/ownership data as control-flow graph of dummy code. In 2012, Chroni and Nikolopoulos developed an ingenious such scheme which was claimed to withstand attacks in the form of a single edge removal. We extend the work of those authors in various aspects. First, we give a formal characterization of the class of graphs generated by their encoding function. Then, we formulate a linear-time algorithm which recovers from ill-intentioned removals of $k \leq 2$ edges, therefore proving their claim. Furthermore, we provide a simpler decoding function and an algorithm to restore watermarks with an arbitrary number of missing edges whenever at all possible. By disclosing and improving upon the resilience of Chroni and Nikolopoulos's watermark, our results reinforce the interest in regarding it as a possible solution to numerous applications.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Complexity of colouring problems restricted to unichord-free and \{square,unichord\}-free graphs

A \emph{unichord} in a graph is an edge that is the unique chord of a cycle. A \emph{square} is an induced cycle on four vertices. A graph is \emph{unichord-free} if none of its edges is a unichord. We give a slight restatement of a known structure theorem for unichord-free graphs and use it to show that, with the only exception of the complete graph $K_4$, every square-free, unichord-free graph of maximum degree~3 can be total-coloured with four colours. Our proof can be turned into a polynomial time algorithm that actually outputs the colouring. This settles the class of square-free, unichord-free graphs as a class for which edge-colouring is NP-complete but total-colouring is polynomial.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Edge-colouring and total-colouring chordless graphs

A graph $G$ is \emph{chordless} if no cycle in $G$ has a chord. In the present work we investigate the chromatic index and total chromatic number of chordless graphs. We describe a known decomposition result for chordless graphs and use it to establish that every chordless graph of maximum degree $Δ\geq 3$ has chromatic index $Δ$ and total chromatic number $Δ+ 1$. The proofs are algorithmic in the sense that we actually output an optimal colouring of a graph instance in polynomial time.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Hierarchical complexity of 2-clique-colouring weakly chordal graphs and perfect graphs having cliques of size at least 3

A clique of a graph is a maximal set of vertices of size at least 2 that induces a complete graph. A $k$-clique-colouring of a graph is a colouring of the vertices with at most $k$ colours such that no clique is monochromatic. Défossez proved that the 2-clique-colouring of perfect graphs is a $Σ_2^P$-complete problem [J. Graph Theory 62 (2009) 139--156]. We strengthen this result by showing that it is still $Σ_2^P$-complete for weakly chordal graphs. We then determine a hierarchy of nested subclasses of weakly chordal graphs whereby each graph class is in a distinct complexity class, namely $Σ_2^P$-complete, $\mathcal{NP}$-complete, and $\mathcal{P}$. We solve an open problem posed by Kratochvíl and Tuza to determine the complexity of 2-clique-colouring of perfect graphs with all cliques having size at least 3 [J. Algorithms 45 (2002), 40--54], proving that it is a $Σ_2^P$-complete problem. We then determine a hierarchy of nested subclasses of perfect graphs with all cliques having size at least 3 whereby each graph class is in a distinct complexity class, namely $Σ_2^P$-complete, $\mathcal{NP}$-complete, and $\mathcal{P}$.

0 citations0 reviewsNo code linkedOpen access