Celina Miraglia Herrera de Figueiredo

Instituição:

Universidade Federal do Rio de Janeiro

Centro:

Centro de Tecnologia

Unidade:

Coordenação dos Programas de Pós-Graduação de Engenharia

Departamento:

Programa de Engenharia de Sistemas/COPPE

ORCID:

https://orcid.org/0000-0002-6393-0876


Formação:

  • University of Waterloo

    | Pós-Doutorado | 1995 - 1996

  • Universidade Federal do Rio de Janeiro

    Engenharia de Sistemas e Computação | Doutorado | 1987 - 1991

  • University of Manchester

    Mathematics | Mestrado | 1985 - 1987

  • Pontifícia Universidade Católica do Rio de Janeiro

    Matemática | Mestrado | 1983 - 1984

  • Pontifícia Universidade Católica do Rio de Janeiro

    Bacharelado em Matemática | Graduação | 1979 - 1982
Laboratórios:
Nenhum laboratório cadastrado
Nuvens de Palavras:
Artigos:

(89.43% artigos com DOI)

Titulo DOI Ano
IFORS' Operational Research Hall of Fame: Clóvis Caesar Gonzaga 10.1111/itor.13432 2024
On the total chromatic number of the direct product of cycles and complete graphs 10.1051/ro/2024045 2024
Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs 10.1002/net.22220 2024
The hardness of recognising poorly matchable graphs and the hunting of the d-snark 10.1051/ro/2024068 2024
On total coloring the direct product of cycles and bipartite direct product of graphs 10.1016/j.disc.2023.113340 2023
On the Computational Difficulty of the Terminal Connection Problem 10.1051/ita/2023002 2023
MaxCut on permutation graphs is NP-complete 10.1002/jgt.22948 2023
On the degree of trees with game chromatic number 4 10.1051/ro/2023150 2023
Maximum Cut on Interval Graphs of Interval Count Four is NP-Complete 10.1007/s00454-023-00508-x 2023
Computing the zig-zag number of directed graphs 10.1016/j.dam.2021.09.013 2022
On total and edge coloring some Kneser graphs 10.1007/s10878-021-00816-z 2022
Compositions, decompositions, and conformability for total coloring on power of cycle graphs 10.1016/j.dam.2021.06.012 2022
A reversible circuit synthesis algorithm with progressive increase of controls in generalized Toffoli gates 10.3897/jucs.69617 2021
Revising Johnson?s table for the 21st century 10.1016/j.dam.2021.05.021 2021
Total tessellation cover: Bounds, hardness, and applications 10.1016/j.dam.2021.09.032 2021
The graph tessellation cover number: Chromatic bounds, efficient algorithms and hardness 10.1016/j.tcs.2019.09.013 2020
On the computational complexity of closest genome problems 10.1016/j.dam.2019.04.002 2020
A multivariate analysis of the strict terminal connection problem 10.1016/j.jcss.2020.02.001 2020
Complexity-separating graph classes for vertex, edge and total colouring 10.1016/j.dam.2019.02.039 2020
On undirected two¿commodity integral flow, disjoint paths and strict terminal connection problems 10.1002/net.21976 2020
THE GUIDE TO NP-COMPLETENESS IS 40 YEARS OLD: AN HOMAGE TO DAVID S. JOHNSON 10.1590/0101-7438.2020.040.00236329 2020
A computational complexity comparative study of graph tessellation problems 10.1016/j.tcs.2020.11.045 2020
On Nordhaus-Gaddum type inequalities for the game chromatic and game coloring numbers 10.1016/j.disc.2019.01.012 2019
On the embedding of cone graphs in the line with distinct distances between neighbors 10.1016/j.dam.2018.05.007 2019
Timber game as a counting problem 10.1016/j.dam.2017.11.011 2019
Using SPQR-trees to speed up recognition algorithms based on 2-cutsets 10.1016/j.dam.2017.01.009 2018
The Sandwich Problem for Decompositions and Almost Monotone Properties 10.1007/s00453-018-0409-6 2018
Sandwich and probe problems for excluding paths 10.1016/j.dam.2018.05.054 2018
Efficient Algorithms for Clique-Colouring and Biclique-Colouring Unichord-Free Graphs 10.1007/s00453-015-0106-7 2017
Shifting Coresets: Obtaining Linear-Time Approximations for Unit Disk Graphs and Other Geometric Intersection Graphs 10.1142/S0218195917500078 2017
The ( k , - ) partitioned probe problem: NP-complete versus polynomial dichotomy 10.1016/j.dam.2017.02.006 2017
The (k,-) unpartitioned probe problem NP-complete versus polynomial dichotomy 10.1016/j.ipl.2015.11.004 2016
On the total coloring of generalized Petersen graphs 10.1016/j.disc.2015.12.010 2016
Hierarchical complexity of 2-clique-colouring weakly chordal graphs and perfect graphs having cliques of size at least 3 10.1016/j.tcs.2016.01.027 2016
Linear-time graph distance and diameter approximation 10.1111/itor.12236 2016
A note on the middle levels problem 10.1016/j.dam.2015.08.001 2016
The cost of perfection for matchings in graphs 10.1016/j.dam.2014.12.006 2016
On the equitable total chromatic number of cubic graphs 10.1016/j.dam.2015.10.013 2016
The Same Upper Bound for Both: The 2-page and the Rectilinear Crossing Numbers of the n -Cube 10.1002/jgt.21910 2016
The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem 10.1016/j.dam.2013.09.004 2015
On probe co-bipartite and probe diamond-free graphs 2015
Biclique-colouring verification complexity and biclique-colouring power graphs 10.1016/j.dam.2014.05.001 2015
Hamiltonian cycles in unitary prefix transposition rearrangement graphs 10.1016/j.dam.2014.05.003 2015
On the recognition of unit disk graphs and the Distance Geometry Problem with Ranges 10.1016/j.dam.2014.08.014 2015
A Faster 1.375-Approximation Algorithm for Sorting by Transpositions* 10.1089/cmb.2014.0298 2015
Complexity of colouring problems restricted to unichord-free and {square,unichord}-free graphs 10.1016/j.dam.2012.02.016 2014
The hunting of a snark with total chromatic number 5 10.1016/j.dam.2013.04.006 2014
Efficient sub-5 approximations for minimum dominating sets in unit disk graphs 10.1016/j.tcs.2014.01.023 2014
Blind-friendly von Neumann's heads or tails 10.4169/amer.math.monthly.121.07.600 2014
Edge-colouring and total-colouring chordless graphs 10.1016/j.disc.2013.03.020 2013
Split clique graph complexity 10.1016/j.tcs.2013.07.020 2013
Advancing the Transposition Distance and Diameter through Lonely Permutations 10.1137/120899753 2013
The P vs. NP-complete dichotomy of some challenging problems in graph theory 10.1016/j.dam.2010.12.014 2012
The total chromatic number of split-indifference graphs 10.1016/j.disc.2012.01.019 2012
A decomposition for total-colouring partial-grids and list-total-colouring outerplanar graphs 10.1002/net.20424 2011
The external constraint 4 nonempty part sandwich problem 10.1016/j.dam.2010.03.015 2011
Transitive orientations in bull-reducible Berge graphs 10.1016/j.dam.2010.05.011 2011
The chain graph sandwich problem 10.1007/s10479-010-0792-0 2011
On the forbidden induced subgraph sandwich problem 10.1016/j.dam.2010.11.010 2011
Total-chromatic number of unichord-free graphs 10.1016/j.dam.2011.03.024 2011
Complexity dichotomy on partial grid recognition 10.1016/j.tcs.2011.01.018 2011
Complexity separating classes for edge-colouring and total-colouring 10.1007/s13173-011-0040-8 2011
Decompositions for edge-coloring join graphs and cobipartite graphs 10.1016/j.dam.2009.01.009 2010
On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs 10.1016/j.dam.2009.01.011 2010
The polynomial dichotomy for three nonempty part sandwich problems 10.1016/j.dam.2009.12.002 2010
2K2 vertex-set partition into nonemptyparts 10.1016/j.disc.2009.11.030 2010
Chromatic index of graphs with no cycle with a unique chord 10.1016/j.tcs.2009.12.018 2010
Unitary toric classes, the reality and desire diagram and sorting by transpositions 10.1137/08074413X 2010
Skewness, splitting numbers and vertex deletion of some toroidal meshes 2009
The complexity of clique graph recognition 10.1016/j.tcs.2009.01.018 2009
Hamiltonian paths in odd graphs 10.2298/AADM0902386B 2009
Enclosing Weighted Points with an Almost-Unit Ball 10.1016/j.ipl.2009.09.001 2009
A new quantum algorithm to solve the minimum searching problem 10.1142/S021974990800361X 2008
An Improved Upper Bound on the Crossing Number of the Hypercube 10.1002/jgt.20330 2008
Helly property, clique graphs, complementary graph classes, and sandwich problems 2008
Tree loop graphs. Computational Molecular Biology Series, Issue V 10.1016/j.dam.2005.01.001 2007
On the generation of bicliques of a graph 10.1016/j.dam.2007.03.017 2007
On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs 10.1016/j.tcs.2007.04.007 2007
Cycles and asteroidal sets in loop graphs 2007
Extended skew partition problem 10.1016/j.disc.2005.12.034 2006
A characterization of P4-Comparability graphs 10.1016/j.disc.2006.05.018 2006
Algorithms for the homogeneous set sandwich problem 10.1007/s00453-005-1198-2 2006
On maximum planar induced subgraph 10.1016/j.dam.2006.03.021 2006
The sandwich problem for cutsets: clique cutset, k-star cutset 10.1016/j.dam.2006.03.023 2006
The pair completion algorithm for the homogeneous set sandwich problem 10.1016/j.ipl.2005.12.010 2006
Reversible Karatsuba's Algorithm 10.3217/jucs-012-05-0499 2006
The non planar vertex deletion of Cn X Cm 2005
The perfection and recognition of bull-reducible Berge graphs 10.1051/ita:2005009 2005
Note on the homogeneous set sandwich problem 10.1016/j.ipl.2004.09.022 2005
Finding H-partitions efficiently 10.1051/ita:2005008 2005
Generating bicliques of a graph in lexicographic order 10.1016/j.tcs.2005.01.014 2005
On the complexity of the approximation of nonplanarity parameters for cubic graphs 10.1016/S0166-218X(03)00370-6 2004
Kinetic hanger 10.1016/j.ipl.2003.10.010 2004
Stable skew partition problem 10.1016/j.dam.2004.01.001 2004
On decision and optimization (k,l)-graph sandwich problems 10.1016/j.dam.2004.02.008 2004
Optimizing bull-free perfect graphs 10.1137/S0895480198339237 2004
Decompositions for the edge colouring of reduced indifference graphs 10.1016/S0304-3975(02)00636-9 2003
Kinetic heap-ordered trees: tight analysis and improved algorithms 10.1016/S0020-0190(02)00366-6 2003
The stable marriage problem with restricted pairs 10.1016/S0304-3975(03)00319-0 2003
The 1-join sandwich problem is NP-complete 10.1016/S0166-218X(01)00246-3 2002
A note on transitive orientations with maximum sets of sources and sinks 10.1016/S0166-218X(01)00283-9 2002
The splitting number and skewness of $C_n \times C_m$ 2002
On Tucker's proof of the Strong Perfect Graph Conjecture for (K4 - e)-free graphs 10.1016/S0012-365X(00)00352-6 2001
Splitting number is NP-complete 10.1016/S0166-218X(00)00220-1 2001
On the structure of bull-free perfect graphs, 2: the weakly chordal case 10.1007/BF01202235 2001
Recognition of quasi-Meyniel graphs 10.1016/S0166-218X(00)00290-0 2001
Finding skew partitions efficiently 10.1006/jagm.1999.1122 2000
On Eggleton and Guy conjectured upper bound for the crossing number of the n-cube 2000
A class of beta-perfect graphs 10.1016/s0012-365x(99)00240-x 2000
Local conditions for edge-coloring 2000
Even and odd pairs in comparability and in P4-comparability graphs 10.1016/S0166-218X(98)00139-5 1999
Total chromatic number and chromatic index of dually chordal graphs 10.1016/S0020-0190(99)00050-2 1999
The homogeneous set sandwich problem 10.1016/s0020-0190(98)00076-3 1998
Sources and sinks in comparability graphs 10.1023/a:1005803107931 1997
On edge-colouring indifference graphs 10.1016/S0304-3975(96)00264-2 1997
Path parity and perfection 10.1016/s0012-365x(96)00174-4 1997
On the structure of bull-free perfect graphs 10.1007/BF01202235 1997
The NP-completeness of multi-partite cutset testing 1996
A linear-time algorithm for proper interval graph recognition 10.1016/0020-0190(95)00133-W 1995
A greedy method for edge-colouring odd maximum degree doubly chordal graphs 1995
Split-Indifference Graphs 1993
On transitive orientations with prescribed sources and sinks 1993
Ordens Indiferenca 1991
Eventos:

(42.86% eventos com DOI)

Titulo DOI Ano
Pebbling in Kneser Graphs 2024
Hyper-heuristics with Path Relinking applied to the Generalised Time-Dependent ATSP in air travel 2023
Parameterized algorithms for Steiner Tree and Dominating Set: bounding the leafage by the vertex leafage 2022
On the Terminal Connection Problem 2021
Maximum cut on interval graphs of interval count four is NP-complete 10.4230/LIPIcs.MFCS.2021.38 2021
On total coloring the direct product of complete graphs 2021
On the chromatic index of complementary prisms 2019
Even-power of cycles with many vertices are Type 1 total colorable 2019
On caterpillars of game chromatic number 4 2019
A general method for forbidden induced sandwich problem NP-completeness 2019
The Graph Tessellation Cover Number: Extremal Bounds, Efficient Algorithms and Hardness 2018
Simple Undirected Two-Commodity Integral Flow with a Unitary Demand 2017
Linear-Time Approximation Algorithms for Unit Disk Graphs 2015
A new reversible circuit synthesis algorithm based on cycle representations of permutations 2015
Using SPQR-trees to speed up algorithms based on 2-cutset decompositions 2015
Hierarchical complexity of 2-clique-colouring weakly chordal graphs and perfect graphs having cliques of size at least 3 2014
A Faster 1.375-Approximation Algorithm for Sorting by Transpositions 2014
Linear Time Approximation for Dominating Sets and Independent Dominating Sets in Unit Disk Graphs 2013
On the 1.375-Approximation Algorithm for Sorting by Transpositions in O(n logn) 2013
The generalized split probe problem 2013
The same upper bound for both: the 2-page and the rectilinear crossing numbers of the n-cube 2013
Clique-colouring and biclique-colouring unichord-free graphs 10.1007/978-3-642-29344-3_45 2012
Transposition diameter and lonely permutations 2012
Biclique-colouring powers of paths and powers of cycles 2012
Snarks with total chromatic number 5 2012
Split clique graph complexity 10.1007/978-3-642-25870-1_3 2011
Hamiltonian Cycles in Kneser Graphs for n=2k+2 10.1016/j.endm.2011.05.050 2011
On coloring problems of snark families 10.1016/j.endm.2011.05.009 2011
Analysis and Implementation of Sorting by Transpositions using Permutation Trees 10.1007/978-3-642-22825-4_6 2011
Advances on the List Stubborn Problem 2010
Complexity dichotomy on degree-constrained VLSI layouts with unit-length edges 10.1016/j.endm.2010.05.050 2010
Total chromatic number of {square,unichord}-free graphs 10.1016/j.endm.2010.05.085 2010
Bounds on the transposition distance for lonely permutations 10.1007/978-3-642-15060-9_4 2010
NP-completeness of determining the total chromatic number of graphs that do not contain a cycle with a unique chord 2009
Skew partition sandwich problem is NP-complete 10.1016/j.endm.2009.11.003 2009
2K2 vertex-set partition into nonemptyparts 10.1016/j.endm.2008.01.050 2008
The polynomial dichotomy for three nonempty part sandwich problems 10.1016/j.endm.2008.01.015 2008
Sufficient conditions for a graph to be edge-colorable with maximum degree colors 10.1016/j.endm.2008.01.013 2008
On the toric graph as a tool to handle the problem of sorting by transpositions 10.1007/978-3-540-85557-6_8 2008
A decomposition for total-coloring graphs of maximum degree 3 2008
The external constraint 4 nonempty part sandwich problem 2008
Edge-coloring graphs with no cycle with a unique chord 2008
On maximizing clique, clique-Helly, and hereditary clique-Helly induced subgraphs 10.1016/j.endm.2008.01.026 2008
Aplicação do Algoritmo de Grover para Problemas NP-Completos 2007
Clique graph recognition is NP-complete 10.1007/11917496_24 2006
Non loop graphs with induced cycles 10.1016/j.endm.2005.05.039 2005
Loop graphs and asteroidal sets 10.1016/j.endm.2005.06.038 2005
On the generation of bicliques of a graph 10.1016/j.endm.2004.03.025 2004
Faster deterministic and randomized algorithms on the Homogeneous Set Sandwich Problem 10.1007/b97914 2004
Simple max-cut for split-indifference graphs and graphs with few P_4's 10.1007/b97914 2004
The sandwich problem for cutsets 10.1016/j.endm.2004.06.035 2004
Nonplanar vertex deletion: maximum degree thresholds for NP/Max SNP-hardness and a 3/4-approx for finding maximum planar induced subgraphs 10.1016/j.endm.2004.06.019 2004
Tree Loop Graphs 10.1016/j.endm.2004.06.003 2004
An improved upper bound on the crossing number of the hypercube 10.1007/b93953 2003
On the Complexity of (k,l)-Graph Sandwich Problems 2002
On the complexity of the approximation of nonplanarity parameters for cubic graphs 10.1016/S1571-0653(04)00214-8 2001
Stable marriages with restricted pairs 10.1016/S1571-0653(04)00213-6 2001
Bull-reducible Berge graphs are perfect 2001
Edge colouring reduced indifference graphs 10.1007/10719839 2000
Finding skew partitions efficiently 10.1007/10719839 2000
The graph sandwich problem for 1-join composition is NP-complete 10.1016/S1571-0653(05)80133-7 2000
Optimal node-degree bounds for the complexity of nonplanarity parameters 1999
Linear-time algorithms for maximum sets of sources and sinks 10.1016/S1571-0653(05)80062-9 1999
Splitting number is NP-complete 1998
The splitting number of the 4--cube 10.1007/BFb0054304 1998
On the edge-colouring of split graphs 1996
On Edge-colouring indifference graphs 10.1007/3-540-59175-3 1995
Even pairs and bull-free perfect graphs 1995
Reconhecimento de Bons Grafos 1992
Maximal Cliques On Split-Indifference Graphs 1992
Sobre Cortes Bipartidos Completos 1992
Perfect Graphs And Computational Complexity 1992
Decomposition Theorems On Perfect Graphs 1991
Even Pairs And Bull-Free Perfect Graphs 1991
Perfect Graphs And The Skew-Partition Conjecture 1991
Grafos Split-Indiferenca 1990
Grafos Perfeitos - Historia e Perspectivas. 1988
Publicações:
Minha Rede: