Search

Your search keyword '"Rosamond, Frances A."' showing total 13 results
Start Over Author "Rosamond, Frances A." Topic vertex cover

Refine your results

more »

more »

13 results on '"Rosamond, Frances A."'

2. Parameterizing by the Number of Numbers

Author

Fellows, Michael R., Gaspers, Serge, Rosamond, Frances A., Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Raman, Venkatesh, editor, and Saurabh, Saket, editor

Published
2010
Full Text
View/download PDF

3. Parameterized Complexity of Stabbing Rectangles and Squares in the Plane

Author

Dom, Michael, Fellows, Michael R., Rosamond, Frances A., Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Das, Sandip, editor, and Uehara, Ryuhei, editor

Published
2009
Full Text
View/download PDF

4. Graph Layout Problems Parameterized by Vertex Cover

Author

Fellows, Michael R., Lokshtanov, Daniel, Misra, Neeldhara, Rosamond, Frances A., Saurabh, Saket, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Hong, Seok-Hee, editor, Nagamochi, Hiroshi, editor, and Fukunaga, Takuro, editor

Published
2008
Full Text
View/download PDF

5. Clustering with Partial Information

Author

Bodlaender, Hans L., Fellows, Michael R., Heggernes, Pinar, Mancini, Federico, Papadopoulos, Charis, Rosamond, Frances, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Ochmański, Edward, editor, and Tyszkiewicz, Jerzy, editor

Published
2008
Full Text
View/download PDF

6. Efficient Parameterized Preprocessing for Cluster Editing

Author

Fellows, Michael, Langston, Michael, Rosamond, Frances, Shaw, Peter, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Csuhaj-Varjú, Erzsébet, editor, and Ésik, Zoltán, editor

Published
2007
Full Text
View/download PDF

7. The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number

Author

Fellows, Michael, Rosamond, Frances, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Cooper, S. Barry, editor, Löwe, Benedikt, editor, and Sorbi, Andrea, editor

Published
2007
Full Text
View/download PDF

8. The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel

Author

Burrage, Kevin, Estivill-Castro, Vladimir, Fellows, Michael, Langston, Michael, Mac, Shev, Rosamond, Frances, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Bodlaender, Hans L., editor, and Langston, Michael A., editor

Published
2006
Full Text
View/download PDF

10. Greedy Localization, Iterative Compression, and Modeled Crown Reductions: New FPT Techniques, an Improved Algorithm for Set Splitting, and a Novel 2k Kernelization for Vertex Cover

Author

Dehne, Frank, Fellows, Mike, Rosamond, Frances, Shaw, Peter, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Downey, Rod, editor, Fellows, Michael, editor, and Dehne, Frank, editor

Published
2004
Full Text
View/download PDF

11. Algorithms, kernels and lower bounds for the Flood-It game parameterized by the vertex cover number.

Author

Fellows, Michael, Protti, Fábio, Rosamond, Frances, da Silva, Maise Dantas, and Souza, Uéverton S.

Subjects
*KERNEL (Mathematics), *ALGORITHMS, *MATHEMATICAL bounds, *PARAMETERS (Statistics), *POLYNOMIALS
Abstract

Flood-It is a combinatorial problem on a colored graph whose aim is to make the graph monochromatic using the minimum number of flooding moves , relatively to a pivot vertex p . A flooding move consists of changing the color of the monochromatic component (maximal monochromatic connected subgraph) containing p . This problem generalizes a combinatorial game named alike which is played on m × n grids. It is known that Flood-It is NP-hard even for 3 × n grids and for instances with bounded number of colors, diameter, treewidth, or pathwidth. In [Fellows, Souza, Protti, Dantas da Silva, Tractability and hardness of flood-filling games on trees, Theoretical Computer Science, 576, 102-116, 2015] it is shown that Flood-It is W[1]-hard when played on trees with bounded number of colors, and the number of leaves is a single parameter. Contrasting with such results, in this work we show that Flood-It is fixed-parameter tractable when parameterized by either the vertex cover number or the neighborhood diversity. Additionally, we prove that Flood-It does not admit a polynomial kernel when the vertex cover number is a single parameter, unless coNP ⊆ NP ∕ poly . Finally, lower bounds based on the (Strong) Exponential Time Hypothesis as well as an upper bound for the required time to solve Flood-It are also provided. [ABSTRACT FROM AUTHOR]

Published
2018
Full Text
View/download PDF

12. On the Fixed-Parameter Tractability of Some Matching Problems Under the Color-Spanning Model

Author

Bereg, Sergey, Ma, Feifei, Wang, Wencheng, Zhang, Jian, Zhu, Binhai, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Xiao, Mingyu, editor, and Rosamond, Frances, editor

Published
2017
Full Text
View/download PDF

13. FPT Algorithms for FVS Parameterized by Split and Cluster Vertex Deletion Sets and Other Parameters

Author

Majumdar, Diptapriyo, Raman, Venkatesh, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Xiao, Mingyu, editor, and Rosamond, Frances, editor

Published
2017
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results