Lilian Markenzon

dblp:21/3703 · DBLP profile ↗
← Back
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
YearPublicationVenuePosition
2021 On feedback vertex set in reducible flow hypergraphs
abstract
A 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
LAGOS3
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
CTW2
2008 A Compact Representation for Chordal Graphs
Lilian Markenzon, Paulo Renato da Costa Pereira
CTW1
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