Two-layer planarization: improving on parameterized algorithmics.
Fernau, Henning (2005)
Journal of Graph Algorithms and Applications
Similarity:
Fernau, Henning (2005)
Journal of Graph Algorithms and Applications
Similarity:
Bhatt, S., Even, S., Greenberg, D., Tayar, R. (2002)
Journal of Graph Algorithms and Applications
Similarity:
Carmignani, Andrea, Di Battista, Giuseppe, Didimo, Walter, Matera, Francesco, Pizzonia, Maurizio (2002)
Journal of Graph Algorithms and Applications
Similarity:
Maheshwari, Anil, Zeh, Norbert (2004)
Journal of Graph Algorithms and Applications
Similarity:
Michael Henning, Christian Löwenstein (2012)
Open Mathematics
Similarity:
Let H be a hypergraph on n vertices and m edges with all edges of size at least four. The transversal number τ(H) of H is the minimum number of vertices that intersect every edge. Lai and Chang [An upper bound for the transversal numbers of 4-uniform hypergraphs, J. Combin. Theory Ser. B, 1990, 50(1), 129–133] proved that τ(H) ≤ 2(n+m)/9, while Chvátal and McDiarmid [Small transversals in hypergraphs, Combinatorica, 1992, 12(1), 19–26] proved that τ(H) ≤ (n + 2m)/6. In this paper, we...
Lubiw, Anna, Petrick, Mark (2011)
Journal of Graph Algorithms and Applications
Similarity:
Eiglsperger, Markus, Siebenhaller, Martin, Kaufmann, Michael (2005)
Journal of Graph Algorithms and Applications
Similarity:
Edith Hemaspaandra, Jörg Rothe, Holger Spakowski (2006)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
For both the edge deletion heuristic and the maximum-degree greedy heuristic, we study the problem of recognizing those graphs for which that heuristic can approximate the size of a minimum vertex cover within a constant factor of , where is a fixed rational number. Our main results are that these problems are complete for the class of problems solvable via parallel access to . To achieve these main results, we also show that the restriction of the vertex cover problem to those graphs...
Boyer, John M., Myrvold, Wendy J. (2004)
Journal of Graph Algorithms and Applications
Similarity:
Duncan, Christian A., Kobourov, Stephen G. (2003)
Journal of Graph Algorithms and Applications
Similarity:
Di Battista, Giuseppe, Patrignani, Maurizio (2000)
Journal of Graph Algorithms and Applications
Similarity:
Milica Stojanović, Milica Vučković (2011)
The Yugoslav Journal of Operations Research
Similarity:
Enrique. Benavent, V. Campos, Angel Corberán, Enrique Mota (1990)
Qüestiió
Similarity:
In this paper we consider the Capacitated Arc Routing Problem, in which a fleet of K vehicles, all of them based on a specific vertex (the depot) and with a known capacity Q, must service a subset of the edges of the graph, with minimum total cost and such that the load assigned to each vehicle does not exceed its capacity. A heuristic algorithm for this problem is proposed consisting of: the selection of K centers, the construction of K connected graphs with associated loads...