Celina M. H. de Figueiredo

According to our database1, Celina M. H. de Figueiredo authored at least 145 papers between 1995 and 2020.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2020
The graph tessellation cover number: Chromatic bounds, efficient algorithms and hardness.
Theor. Comput. Sci., 2020

On the computational complexity of closest genome problems.
Discret. Appl. Math., 2020

2019
Even-power of Cycles With Many Vertices are Type 1 Total Colorable.
Proceedings of the tenth Latin and American Algorithms, Graphs and Optimization Symposium, 2019

On Caterpillars of Game Chromatic Number 4.
Proceedings of the tenth Latin and American Algorithms, Graphs and Optimization Symposium, 2019

A General Method for Forbidden Induced Subgraph Sandwich Problem NP-completeness.
Proceedings of the tenth Latin and American Algorithms, Graphs and Optimization Symposium, 2019

On Nordhaus-Gaddum type inequalities for the game chromatic and game coloring numbers.
Discret. Math., 2019

On the embedding of cone graphs in the line with distinct distances between neighbors.
Discret. Appl. Math., 2019

Timber game as a counting problem.
Discret. Appl. Math., 2019

The Tessellation Cover Number of Good Tessellable Graphs.
CoRR, 2019

2018
Using SPQR-trees to speed up recognition algorithms based on 2-cutsets.
Discret. Appl. Math., 2018

Sandwich and probe problems for excluding paths.
Discret. Appl. Math., 2018

The partitioned probe problem: NP-complete versus polynomial dichotomy.
Discret. Appl. Math., 2018

The Sandwich Problem for Decompositions and Almost Monotone Properties.
Algorithmica, 2018

The Graph Tessellation Cover Number: Extremal Bounds, Efficient Algorithms and Hardness.
Proceedings of the LATIN 2018: Theoretical Informatics, 2018

2017
Shifting Coresets: Obtaining Linear-Time Approximations for Unit Disk Graphs and Other Geometric Intersection Graphs.
Int. J. Comput. Geometry Appl., 2017

Simple Undirected Two-Commodity Integral Flow with a Unitary Demand.
Electron. Notes Discret. Math., 2017

The tessellation problem of quantum walks.
CoRR, 2017

Efficient Algorithms for Clique-Colouring and Biclique-Colouring Unichord-Free Graphs.
Algorithmica, 2017

2016
Hierarchical complexity of 2-clique-colouring weakly chordal graphs and perfect graphs having cliques of size at least 3.
Theor. Comput. Sci., 2016

The Same Upper Bound for Both: The 2-page and the Rectilinear Crossing Numbers of the n-Cube.
Journal of Graph Theory, 2016

Linear-time graph distance and diameter approximation.
ITOR, 2016

The (k, ℓ) unpartitioned probe problem NP-complete versus polynomial dichotomy.
Inf. Process. Lett., 2016

On the total coloring of generalized Petersen graphs.
Discret. Math., 2016

A note on the middle levels problem.
Discret. Appl. Math., 2016

On the equitable total chromatic number of cubic graphs.
Discret. Appl. Math., 2016

The cost of perfection for matchings in graphs.
Discret. Appl. Math., 2016

2015
A Faster 1.375-Approximation Algorithm for Sorting by Transpositions*.
Journal of Computational Biology, 2015

A new reversible circuit synthesis algorithm based on cycle representations of permutations.
Electron. Notes Discret. Math., 2015

Using SPQR-trees to speed up algorithms based on 2-cutset decompositions.
Electron. Notes Discret. Math., 2015

On probe co-bipartite and probe diamond-free graphs.
Discrete Mathematics & Theoretical Computer Science, 2015

Hamiltonian cycles in unitary prefix transposition rearrangement graphs.
Discret. Appl. Math., 2015

On the recognition of unit disk graphs and the Distance Geometry Problem with Ranges.
Discret. Appl. Math., 2015

Biclique-colouring verification complexity and biclique-colouring power graphs.
Discret. Appl. Math., 2015

The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem.
Discret. Appl. Math., 2015

Timber Game with Caterpillars.
Proceedings of the 13th Cologne Twente Workshop on Graphs and Combinatorial Optimization, 2015

Sorting Separable Permutations by Restricted Multi-break Rearrangements.
Proceedings of the 13th Cologne Twente Workshop on Graphs and Combinatorial Optimization, 2015

2014
Efficient sub-5 approximations for minimum dominating sets in unit disk graphs.
Theor. Comput. Sci., 2014

Blind-friendly von Neumann's Heads or Tails.
The American Mathematical Monthly, 2014

The hunting of a snark with total chromatic number 5.
Discret. Appl. Math., 2014

Complexity of colouring problems restricted to unichord-free and { square, unichord }-free graphs.
Discret. Appl. Math., 2014

Linear-Time Approximation Algorithms for Unit Disk Graphs.
Proceedings of the Approximation and Online Algorithms - 12th International Workshop, 2014

2013
Split clique graph complexity.
Theor. Comput. Sci., 2013

Advancing the Transposition Distance and Diameter through Lonely Permutations.
SIAM J. Discrete Math., 2013

The generalized split probe problem.
Electron. Notes Discret. Math., 2013

Edge-colouring and total-colouring chordless graphs.
Discret. Math., 2013

On the 1.375-Approximation Algorithm for Sorting by Transpositions in O(n logn) Time.
Proceedings of the Advances in Bioinformatics and Computational Biology, 2013

The Same Upper Bound for Both: The 2-Page and the Rectilinear Crossing Numbers of the n-Cube.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2013

On total coloring and equitable total coloring of cubic graphs with large girth.
Proceedings of the 12th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2013

2012
Graph theory and algorithms - Fourth Latin-American Workshop on Cliques in Graphs.
J. Braz. Comp. Soc., 2012

The total chromatic number of split-indifference graphs.
Discret. Math., 2012

The P versus NP-complete dichotomy of some challenging problems in graph theory.
Discret. Appl. Math., 2012

Cayley graphs and analysis of quantum cost for reversible circuit synthesis
CoRR, 2012

The Cost of Perfection for Matchings in Graphs
CoRR, 2012

Transposition Diameter and Lonely Permutations.
Proceedings of the Advances in Bioinformatics and Computational Biology, 2012

Linear Time Approximation for Dominating Sets and Independent Dominating Sets in Unit Disk Graphs.
Proceedings of the Approximation and Online Algorithms - 10th International Workshop, 2012

Clique-Colouring and Biclique-Colouring Unichord-Free Graphs.
Proceedings of the LATIN 2012: Theoretical Informatics, 2012

Biclique-colouring - Powers of Paths and Powers of Cycles.
Proceedings of the 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2012

Snarks with Total Chromatic Number 5.
Proceedings of the 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2012

2011
Complexity dichotomy on partial grid recognition.
Theor. Comput. Sci., 2011

A decomposition for total-coloring partial-grids and list-total-coloring outerplanar graphs.
Networks, 2011

Complexity separating classes for edge-colouring and total-colouring.
J. Braz. Comp. Soc., 2011

On Coloring Problems of Snark Families.
Electron. Notes Discret. Math., 2011

Hamiltonian Cycles in Kneser Graphs for n=2k+2.
Electron. Notes Discret. Math., 2011

The external constraint 4 nonempty part sandwich problem.
Discret. Appl. Math., 2011

Total chromatic number of unichord-free graphs.
Discret. Appl. Math., 2011

Transitive orientations in bull-reducible Berge graphs.
Discret. Appl. Math., 2011

On the forbidden induced subgraph sandwich problem.
Discret. Appl. Math., 2011

The chain graph sandwich problem.
Annals OR, 2011

Analysis and Implementation of Sorting by Transpositions Using Permutation Trees.
Proceedings of the Advances in Bioinformatics and Computational Biology, 2011

2010
Chromatic index of graphs with no cycle with a unique chord.
Theor. Comput. Sci., 2010

Unitary Toric Classes, the Reality and Desire Diagram, and Sorting by Transpositions.
SIAM J. Discrete Math., 2010

Complexity dichotomy on degree-constrained VLSI layouts with unit-length edges.
Electron. Notes Discret. Math., 2010

Total chromatic number of {square, unichord}-free graphs.
Electron. Notes Discret. Math., 2010

2K2 vertex-set partition into nonempty parts.
Discret. Math., 2010

Decompositions for edge-coloring join graphs and cobipartite graphs.
Discret. Appl. Math., 2010

Bounds on the Transposition Distance for Lonely Permutations.
Proceedings of the Advances in Bioinformatics and Computational Biology, 2010

Chromatic Index of Chordless Graphs.
Proceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2010

Advances on the List Stubborn Problem.
Proceedings of the Theory of Computing 2010, 2010

2009
The complexity of clique graph recognition.
Theor. Comput. Sci., 2009

Enclosing weighted points with an almost-unit ball.
Inf. Process. Lett., 2009

Skew partition sandwich problem is NP-complete.
Electron. Notes Discret. Math., 2009

Skewness, splitting number and vertex deletion of some toroidal meshes.
Ars Comb., 2009

NP-Completeness of Determining the Total Chromatic Number of Graphs that do not Contain a Cycle with a Unique Chord.
Proceedings of the 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2009

2008
An improved upper bound on the crossing number of the hypercube.
Journal of Graph Theory, 2008

Helly Property, Clique Graphs, Complementary Graph Classes, and Sandwich Problems.
J. Braz. Comp. Soc., 2008

The polynomial dichotomy for three nonempty part sandwich problems.
Electron. Notes Discret. Math., 2008

Sufficient conditions for a graph to be edge-colorable with maximum degree colors.
Electron. Notes Discret. Math., 2008

2K2 vertex-set partition into nonempty parts.
Electron. Notes Discret. Math., 2008

On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs.
Electron. Notes Discret. Math., 2008

On the Toric Graph as a Tool to Handle the Problem of Sorting by Transpositions.
Proceedings of the Advances in Bioinformatics and Computational Biology, 2008

A decomposition for total-coloring graphs of maximum degree 3.
Proceedings of the Seventh Cologne Twente Workshop on Graphs and Combinatorial Optimization, 2008

2007
On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs.
Theor. Comput. Sci., 2007

2006
Reversible Karatsuba's Algorithm.
J. UCS, 2006

The Pair Completion algorithm for the Homogeneous Set Sandwich Problem.
Inf. Process. Lett., 2006

A characterization of P4-comparability graphs.
Discret. Math., 2006

Extended skew partition problem.
Discret. Math., 2006

The sandwich problem for cutsets: Clique cutset, k-star cutset.
Discret. Appl. Math., 2006

On maximum planar induced subgraphs.
Discret. Appl. Math., 2006

Algorithms for the Homogeneous Set Sandwich Problem.
Algorithmica, 2006

Clique Graph Recognition Is NP-Complete.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2006

2005
Generating bicliques of a graph in lexicographic order.
Theor. Comput. Sci., 2005

The perfection and recognition of bull-reducible Berge graphs.
ITA, 2005

Finding H-partitions efficiently.
ITA, 2005

Note on the Homogeneous Set Sandwich Problem.
Inf. Process. Lett., 2005

Preface.
Electron. Notes Discret. Math., 2005

Non loop graphs with induced cycles.
Electron. Notes Discret. Math., 2005

Loop Graphs and Asteroidal Sets.
Electron. Notes Discret. Math., 2005

The non planar vertex deletion of Cn x Cm.
Ars Comb., 2005

2004
Optimizing Bull-Free Perfect Graphs.
SIAM J. Discrete Math., 2004

Kinetic hanger.
Inf. Process. Lett., 2004

The sandwich problem for cutsets.
Electron. Notes Discret. Math., 2004

Nonplanar vertex deletion: maximum degree thresholds for NP/Max SNP-hardness and a I-approximation for finding maximum planar induced subgraphs.
Electron. Notes Discret. Math., 2004

On the generation of bicliques of a graph.
Electron. Notes Discret. Math., 2004

Tree Loop Graphs.
Electron. Notes Discret. Math., 2004

Stable skew partition problem.
Discret. Appl. Math., 2004

On decision and optimization (k, l)-graph sandwich problems.
Discret. Appl. Math., 2004

Faster Deterministic and Randomized Algorithms on the Homogeneous Set Sandwich Problem.
Proceedings of the Experimental and Efficient Algorithms, Third International Workshop, 2004

Simple Max-Cut for Split-Indifference Graphs and Graphs with Few P4's.
Proceedings of the Experimental and Efficient Algorithms, Third International Workshop, 2004

2003
Decompositions for the edge colouring of reduced indifference graphs.
Theor. Comput. Sci., 2003

The stable marriage problem with restricted pairs.
Theor. Comput. Sci., 2003

Kinetic heap-ordered trees: Tight analysis and improved algorithms.
Inf. Process. Lett., 2003

2002
A note on transitive orientations with maximum sets of sources and sinks.
Discret. Appl. Math., 2002

The splitting number and skewness of Cn x Cm.
Ars Comb., 2002

On the Complexity of (k, l)-Graph Sandwich Problems.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2002

2001
On the Structure of Bull-Free Perfect Graphs, 2: the Weakly Chordal Case.
Graphs and Combinatorics, 2001

On the complexity of the approximation of nonplanarity parameters for cubic graphs.
Electron. Notes Discret. Math., 2001

Bull-Reducible Berge Graphs are Perfect.
Electron. Notes Discret. Math., 2001

Stable marriages with restricted pairs.
Electron. Notes Discret. Math., 2001

On Tucker's proof of the strong perfect graph conjecture for (K4-e)-free graphs.
Discret. Math., 2001

Recognition of quasi-Meyniel graphs.
Discret. Appl. Math., 2001

SPLITTING NUMBER is NP-complete.
Discret. Appl. Math., 2001

2000
Finding Skew Partitions Efficiently.
J. Algorithms, 2000

The graph sandwich problem for 1-join composition is NP-complete.
Electron. Notes Discret. Math., 2000

A class of ?-perfect graphs.
Discret. Math., 2000

Edge Colouring Reduced Indifference Graphs.
Proceedings of the LATIN 2000: Theoretical Informatics, 2000

1999
Total-Chromatic Number and Chromatic Index of Dually Chordal Graphs.
Inf. Process. Lett., 1999

Linear-time Algorithms for Maximum Sets of Sources and sinks.
Electron. Notes Discret. Math., 1999

Even and Odd Pairs in Comparability and in P4-comparability Graphs.
Discret. Appl. Math., 1999

Optimal Node-Degree Bounds for the Complexity of Nonplanarity Parameters.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

1998
The Homogeneous Set Sandwich Problem.
Inf. Process. Lett., 1998

The Splitting Number of the 4-Cube.
Proceedings of the LATIN '98: Theoretical Informatics, 1998

1997
On Edge-Colouring Indifference Graphs.
Theor. Comput. Sci., 1997

On the structure of bull-free perfect graphs.
Graphs and Combinatorics, 1997

Path parity and perfection.
Discret. Math., 1997

1995
A Linear-Time Algorithm for Proper Interval Graph Recognition.
Inf. Process. Lett., 1995


  Loading...