Nicola Apollonio
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Nicola Apollonio has a total of 7 co-authors. Here are the top co-authors by number of shared publications:
B. Simeone
Dip. Statistica, Probabilità e Statistiche Applicate Università di Roma “La Sapienza”, piazzale Aldo Moro 5, 00185 Roma, Italy
1 shared publicationBruno Simeone
1 shared publication- Federica Ricca
Università degli studi di Roma La Sapienza
1 shared publication - Isabella Lari
Dipartimento di Scienze Statistiche Università di Roma "La Sapienza" piazzale Aldo Moro 5 00185 Roma Italy
1 shared publication - Justo Puerto
Institute of Mathematics (IMUS), Universidad de Sevilla, Sevilla, Spain
1 shared publication - Massimiliano Caramia
Dipartimento di Ingegneria dell’Impresa, University of Rome Tor Vergata, Rome, Italy
1 shared publication
Latest Publications
- 1 March 2014
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 165, 37-48
The maximum vertex coverage problem on bipartite graphs
- 1 March 2014
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 165, 37-48
The maximum vertex coverage problem on bipartite graphs
- 6 July 2011
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 159 (11) , 1166-1175
Recognizing Helly Edge-Path-Tree graphs and their clique graphs
- 6 July 2011
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 159 (11) , 1166-1175
Recognizing Helly Edge-Path-Tree graphs and their clique graphs
- 28 June 2009
- Published by Elsevier in Discrete Mathematics
- Vol. 309 (12) , 4181-4184
Integrality properties of edge path tree families
- 28 June 2009
- Published by Elsevier in Discrete Mathematics
- Vol. 309 (12) , 4181-4184
Integrality properties of edge path tree families
- Open Access
- 6 June 2009
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 157 (11) , 2525-2535
On the complexity of recognizing directed path families
- 6 June 2009
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 157 (11) , 2525-2535
Open AccessOn the complexity of recognizing directed path families
- Open Access
Polynomial algorithms for partitioning a tree into single‐center subtrees to minimize flat service costs
This paper deals with the following graph partitioning problem. Consider a connected graph with n nodes, p of which are centers, while the remaining ones are units. For each unit‐center pair there is a fixed service cost and the goal is to find a partition into connected components such that each component contains only one center and the total service cost is minimum. This problem is known to be NP‐hard on general graphs, and here we show that it remains such even if the service cost is monotone and the graph is bipartite. However, in this paper we derive some polynomial time algorithms for trees. For this class of graphs we provide several reformulations of the problem as integer linear programs proving the integrality of the corresponding polyhedra. As a consequence, the tree partitioning problem can be solved in polynomial time either by linear programming or by suitable convex nondifferentiable optimization algorithms. Moreover, we develop a dynamic programming algorithm, whose recursion is based on sequences of minimum weight closure problems, which solves the problem on trees in O(np) time. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008
Open AccessPolynomial algorithms for partitioning a tree into single‐center subtrees to minimize flat service costs
This paper deals with the following graph partitioning problem. Consider a connected graph with n nodes, p of which are centers, while the remaining ones are units. For each unit‐center pair there is a fixed service cost and the goal is to find a partition into connected components such that each component contains only one center and the total service cost is minimum. This problem is known to be NP‐hard on general graphs, and here we show that it remains such even if the service cost is monotone and the graph is bipartite. However, in this paper we derive some polynomial time algorithms for trees. For this class of graphs we provide several reformulations of the problem as integer linear programs proving the integrality of the corresponding polyhedra. As a consequence, the tree partitioning problem can be solved in polynomial time either by linear programming or by suitable convex nondifferentiable optimization algorithms. Moreover, we develop a dynamic programming algorithm, whose recursion is based on sequences of minimum weight closure problems, which solves the problem on trees in O(np) time. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008