VLDB 2026 Research / reviewers in the wild / expert
Lilian Markenzon
dblp:21/3703
· DBLP profile ↗
11ranked-venue papers
4as first author
1since 2021 · last 2021
0000-0001-7524-6812ORCID · corroborated
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 11 · 4 first-author · 1 since 2021
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2021 | On feedback vertex set in reducible flow hypergraphsabstractA directed hypergraph H = (V, A) is a finite set of vertices V and a set of hyper-arcs A, where each hyper-arc is an ordered pair of nonempty subsets of vertices. A flow hypergraph H = (V, A, s) is a triple, such that (V, A) is a directed hypergraph, s e V is a distinguished vertex such that s reaches every vertex of V. Reducible flow hypergraphs are a generalization of Hecht and Ullman’s reducible flowgraphs. The feedback vertex set (fvs) decision problem has a directed hypergraph H and an integer k ≥ 0 as input and the question is whether there is V'⊆V, |V' |≤k such that H\V' is an acyclic directed hypergraph. It is known that fvs is polynomial time solvable for reducible flowgraphs. In this article we prove that fvs is NP-complete for reducible flow hypergraphs showing a reduction from 3-satisfiability problem with at most 3 occurrences per variable (3sat3-). We exhibit a polynomial-time ∆-approximation for fvs in reducible flow hypergraphs, where ∆ is the maximum number of hyper-arcs adjacent to a vertex of H. Luérbio Faria, André Luiz Pires Guedes, Lilian Markenzon |
LAGOS | 3 |
| 2020 | Non-inclusion and other subclasses of chordal graphs
Lilian Markenzon |
Discret. Appl. Math. | 1 |
| 2019 | Block-indifference graphs: Characterization, structural and spectral properties
Nair Maria Maia de Abreu, Cláudia Marcela Justel, Lilian Markenzon, Carla Silva Oliveira, Christina Fraga Esteves Maciel Waga |
Discret. Appl. Math. | 3 |
| 2015 | New results on ptolemaic graphs
Lilian Markenzon, Christina Fraga Esteves Maciel Waga |
Discret. Appl. Math. | 1 |
| 2014 | Generating and counting unlabeled k-path graphs
Paulo Renato da Costa Pereira, Alex de V. Garcia, Lilian Markenzon |
Discret. Appl. Math. | 3 |
| 2011 | Flow hypergraph reducibility
André Luiz Pires Guedes, Lilian Markenzon, Luérbio Faria |
Discret. Appl. Math. | 2 |
| 2009 | Recognition of Reducible Flow Hypergraphs
André Luiz Pires Guedes, Lilian Markenzon, Luérbio Faria |
CTW | 2 |
| 2008 | A Compact Representation for Chordal Graphs
Lilian Markenzon, Paulo Renato da Costa Pereira |
CTW | 1 |
| 2008 | A clique-difference encoding scheme for labelled k-path graphs
Paulo Renato da Costa Pereira, Lilian Markenzon, Oswaldo Vernet |
Discret. Appl. Math. | 2 |
| 2006 | Subclasses of k-trees: Characterization and recognition
Lilian Markenzon, Cláudia Marcela Justel, N. Paciornik |
Discret. Appl. Math. | 1 |
| 2004 | Solving problems for maximal reducible flowgraphs
Oswaldo Vernet, Lilian Markenzon |
Discret. Appl. Math. | 2 |