Search

Your search keyword '"Rosamond, Frances A."' showing total 414 results
Start Over Author "Rosamond, Frances A."
414 results on '"Rosamond, Frances A."'

2. Open Problems in (Hyper)Graph Decomposition

Author

Ajwani, Deepak, Bisseling, Rob H., Casel, Katrin, Çatalyürek, Ümit V., Chevalier, Cédric, Chudigiewitsch, Florian, Faraj, Marcelo Fonseca, Fellows, Michael, Gottesbüren, Lars, Heuer, Tobias, Karypis, George, Kaya, Kamer, Lacki, Jakub, Langguth, Johannes, Li, Xiaoye Sherry, Mayer, Ruben, Meintrup, Johannes, Mizutani, Yosuke, Pellegrini, François, Petrini, Fabrizio, Rosamond, Frances, Safro, Ilya, Schlag, Sebastian, Schulz, Christian, Sharma, Roohani, Strash, Darren, Sullivan, Blair D., Uçar, Bora, and Yzelman, Albert-Jan

Subjects
Computer Science - Data Structures and Algorithms
Abstract

Large networks are useful in a wide range of applications. Sometimes problem instances are composed of billions of entities. Decomposing and analyzing these structures helps us gain new insights about our surroundings. Even if the final application concerns a different problem (such as traversal, finding paths, trees, and flows), decomposing large graphs is often an important subproblem for complexity reduction or parallelization. This report is a summary of discussions that happened at Dagstuhl seminar 23331 on "Recent Trends in Graph Decomposition" and presents currently open problems and future directions in the area of (hyper)graph decomposition.

Published
2023

3. On Solution Discovery via Reconfiguration

Author

Fellows, Michael R., Grobler, Mario, Megow, Nicole, Mouawad, Amer E., Ramamoorthi, Vijayaragunathan, Rosamond, Frances A., Schmand, Daniel, and Siebertz, Sebastian

Subjects
Computer Science - Computational Complexity, Computer Science - Discrete Mathematics, Computer Science - Data Structures and Algorithms
Abstract

The dynamics of real-world applications and systems require efficient methods for improving infeasible solutions or restoring corrupted ones by making modifications to the current state of a system in a restricted way. We propose a new framework of solution discovery via reconfiguration for constructing a feasible solution for a given problem by executing a sequence of small modifications starting from a given state. Our framework integrates and formalizes different aspects of classical local search, reoptimization, and combinatorial reconfiguration. We exemplify our framework on a multitude of fundamental combinatorial problems, namely Vertex Cover, Independent Set, Dominating Set, and Coloring. We study the classical as well as the parameterized complexity of the solution discovery variants of those problems and explore the boundary between tractable and intractable instances.

Published
2023

4. Parameterized String Equations

Author

Bulteau, Laurent, Fellows, Michael R., Komusiewicz, Christian, and Rosamond, Frances

Subjects
Computer Science - Computational Complexity
Abstract

We study systems of String Equations where block variables need to be assigned strings so that their concatenation gives a specified target string. We investigate this problem under a multivariate complexity framework, searching for tractable special cases such as systems of equations with few block variables or few equations. Our main results include a polynomial-time algorithm for size-2 equations, and hardness for size-3 equations, as well as hardness for systems of two equations, even with tight constraints on the block variables. We also study a variant where few deletions are allowed in the target string, and give XP algorithms in this setting when the number of block variables is constant.

Published
2021

5. On Solution Discovery via Reconfiguration

Author

Fellows, Michael R., primary, Grobler, Mario, additional, Megow, Nicole, additional, Mouawad, Amer E., additional, Ramamoorthi, Vijayaragunathan, additional, Rosamond, Frances A., additional, Schmand, Daniel, additional, and Siebertz, Sebastian, additional

Published
2023
Full Text
View/download PDF

6. On the Parameterized Complexity of the Structure of Lineal Topologies (Depth-First Spanning Trees) of Finite Graphs: The Number of Leaves

Author

Sam, Emmanuel, Fellows, Michael, Rosamond, Frances, Golovach, Petr A., Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, and Mavronicolas, Marios, editor

Published
2023
Full Text
View/download PDF

7. Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory

Author

Baste, Julien, Fellows, Michael R., Jaffke, Lars, Masařík, Tomáš, Oliveira, Mateus de Oliveira, Philip, Geevarghese, and Rosamond, Frances A.

Subjects
Computer Science - Data Structures and Algorithms, Computer Science - Discrete Mathematics, 05C85
Abstract

When modeling an application of practical relevance as an instance of a combinatorial problem X, we are often interested not merely in finding one optimal solution for that instance, but in finding a sufficiently diverse collection of good solutions. In this work we initiate a systematic study of diversity from the point of view of fixed-parameter tractability theory. First, we consider an intuitive notion of diversity of a collection of solutions which suits a large variety of combinatorial problems of practical interest. We then present an algorithmic framework which --automatically-- converts a tree-decomposition-based dynamic programming algorithm for a given combinatorial problem X into a dynamic programming algorithm for the diverse version of X. Surprisingly, our algorithm has a polynomial dependence on the diversity parameter., Comment: Accepted to Twenty-Ninth International Joint Conference on Artificial Intelligence, {IJCAI} 2020, 16 pages

Published
2019
Full Text
View/download PDF

8. Computational Thinking Enrichment: Public-Key Cryptography

Author

Rosamond, Frances

Abstract

The Computer Science Unplugged activities and project has been an influential STEM (Science, Technology, Engineering & Mathematics) initiative, providing enrichment and teaching activities supporting computational thinking. Many of its activities are suitable for children. One of the most popular Unplugged activities is "Kid Krypto", invented by Mike Fellows and Neal Koblitz. Kid Krypto demonstrates the mathematics underlying public-key cryptography without using advanced mathematics. The paper gives an example of a Kid Krypto-style encryption system that is based on disjoint cycles in a graph or network and which is accessible to a very young audience. Also described is the original Kid Krypto system which is based on a version of dominating set called perfect code. The paper urges research scientists to participate in mathematical sciences communication and outreach.

Published
2018

9. What is known about Vertex Cover Kernelization?

Author

Fellows, Michael R., Jaffke, Lars, Király, Aliz Izabella, Rosamond, Frances A., and Weller, Mathias

Subjects
Computer Science - Data Structures and Algorithms, Computer Science - Artificial Intelligence, F.2.2, G.2.2
Abstract

We are pleased to dedicate this survey on kernelization of the Vertex Cover problem, to Professor Juraj Hromkovi\v{c} on the occasion of his 60th birthday. The Vertex Cover problem is often referred to as the Drosophila of parameterized complexity. It enjoys a long history. New and worthy perspectives will always be demonstrated first with concrete results here. This survey discusses several research directions in Vertex Cover kernelization. The Barrier Degree of Vertex Cover kernelization is discussed. We have reduction rules that kernelize vertices of small degree, including in this paper new results that reduce graphs almost to minimum degree five. Can this process go on forever? What is the minimum vertex-degree barrier for polynomial-time kernelization? Assuming the Exponential-Time Hypothesis, there is a minimum degree barrier. The idea of automated kernelization is discussed. We here report the first experimental results of an AI-guided branching algorithm for Vertex Cover whose logic seems amenable for application in finding reduction rules to kernelize small-degree vertices. The survey highlights a central open problem in parameterized complexity. Happy Birthday, Juraj!, Comment: 25 pages, 10 figures. Appeared in volume 11011 of LNCS, pages 330-356, see Reference [29] in the text. Compared to [29], this arXiv-upload contains a fixed version of Reduction R.8, the order of presentation of Reductions R.6 and R.7 has been switched, and a few observations have been added in Section 3

Published
2018

10. Collaborating with Hans: Some Remaining Wonderments

Author

Fellows, Michael R., Rosamond, Frances A., Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Fomin, Fedor V., editor, Kratsch, Stefan, editor, and van Leeuwen, Erik Jan, editor

Published
2020
Full Text
View/download PDF

11. 7th International Conference on Creative Mathematical Sciences Communication (CMSC'24)

Author

Rosamond, Frances A. and Rosamond, Frances A.

Abstract

The 7th International Creative Mathematical Sciences Communication (CMSC) conference is scheduled for October 2024 in Trier, Germany. Initiated in Darwin, Australia in 2013, CMSC aims to explore novel methods of imparting computational thinking to diverse audiences including non-specialists, modern citizens, and children. Participants from around the world and from various and interdisciplinary disciplines such as science, education, dance, drama, and visual arts convene to exchange ideas, present experimental approaches, and collaborate on engaging children in the exploration of ongoing, unresolved research challenges.

Published
2024

12. Recent Trends in Graph Decomposition (Dagstuhl Seminar 23331)

Author

George Karypis and Christian Schulz and Darren Strash and Deepak Ajwani and Rob H. Bisseling and Katrin Casel and Ümit V. Çatalyürek and Cédric Chevalier and Florian Chudigiewitsch and Marcelo Fonseca Faraj and Michael Fellows and Lars Gottesbüren and Tobias Heuer and Kamer Kaya and Jakub Lacki and Johannes Langguth and Xiaoye Sherry Li and Ruben Mayer and Johannes Meintrup and Yosuke Mizutani and François Pellegrini and Fabrizio Petrini and Frances Rosamond and Ilya Safro and Sebastian Schlag and Roohani Sharma and Blair D. Sullivan and Bora Uçar and Albert-Jan Yzelman, Karypis, George, Schulz, Christian, Strash, Darren, Ajwani, Deepak, Bisseling, Rob H., Casel, Katrin, Çatalyürek, Ümit V., Chevalier, Cédric, Chudigiewitsch, Florian, Faraj, Marcelo Fonseca, Fellows, Michael, Gottesbüren, Lars, Heuer, Tobias, Kaya, Kamer, Lacki, Jakub, Langguth, Johannes, Li, Xiaoye Sherry, Mayer, Ruben, Meintrup, Johannes, Mizutani, Yosuke, Pellegrini, François, Petrini, Fabrizio, Rosamond, Frances, Safro, Ilya, Schlag, Sebastian, Sharma, Roohani, Sullivan, Blair D., Uçar, Bora, Yzelman, Albert-Jan, George Karypis and Christian Schulz and Darren Strash and Deepak Ajwani and Rob H. Bisseling and Katrin Casel and Ümit V. Çatalyürek and Cédric Chevalier and Florian Chudigiewitsch and Marcelo Fonseca Faraj and Michael Fellows and Lars Gottesbüren and Tobias Heuer and Kamer Kaya and Jakub Lacki and Johannes Langguth and Xiaoye Sherry Li and Ruben Mayer and Johannes Meintrup and Yosuke Mizutani and François Pellegrini and Fabrizio Petrini and Frances Rosamond and Ilya Safro and Sebastian Schlag and Roohani Sharma and Blair D. Sullivan and Bora Uçar and Albert-Jan Yzelman, Karypis, George, Schulz, Christian, Strash, Darren, Ajwani, Deepak, Bisseling, Rob H., Casel, Katrin, Çatalyürek, Ümit V., Chevalier, Cédric, Chudigiewitsch, Florian, Faraj, Marcelo Fonseca, Fellows, Michael, Gottesbüren, Lars, Heuer, Tobias, Kaya, Kamer, Lacki, Jakub, Langguth, Johannes, Li, Xiaoye Sherry, Mayer, Ruben, Meintrup, Johannes, Mizutani, Yosuke, Pellegrini, François, Petrini, Fabrizio, Rosamond, Frances, Safro, Ilya, Schlag, Sebastian, Sharma, Roohani, Sullivan, Blair D., Uçar, Bora, and Yzelman, Albert-Jan

Abstract

This report documents the program and the outcomes of Dagstuhl Seminar 23331 "Recent Trends in Graph Decomposition", which took place from 13. August to 18. August, 2023. The seminar brought together 33 experts from academia and industry to discuss graph decomposition, a pivotal technique for handling massive graphs in applications such as social networks and scientific simulations. The seminar addressed the challenges posed by contemporary hardware designs, the potential of deep neural networks and reinforcement learning in developing heuristics, the unique optimization requirements of large sparse data, and the need for scalable algorithms suitable for emerging architectures. Through presentations, discussions, and collaborative sessions, the event fostered an exchange of innovative ideas, leading to the creation of community notes highlighting key open problems in the field.

Published
2024
Full Text
View/download PDF

13. Myhill-Nerode methods for hypergraphs

Author

van Bevern, René, Downey, Rodney G., Fellows, Michael R., Gaspers, Serge, and Rosamond, Frances A.

Subjects
Computer Science - Discrete Mathematics, Computer Science - Data Structures and Algorithms, Computer Science - Formal Languages and Automata Theory, Mathematics - Combinatorics, 68Q45, F.1.1, F.2.2, F.4.2, G.2.1, G.2.3
Abstract

We give an analog of the Myhill-Nerode methods from formal language theory for hypergraphs and use it to derive the following results for two NP-hard hypergraph problems: * We provide an algorithm for testing whether a hypergraph has cutwidth at most k that runs in linear time for constant k. In terms of parameterized complexity theory, the problem is fixed-parameter linear parameterized by k. * We show that it is not expressible in monadic second-order logic whether a hypergraph has bounded (fractional, generalized) hypertree width. The proof leads us to conjecture that, in terms of parameterized complexity theory, these problems are W[1]-hard parameterized by the incidence treewidth (the treewidth of the incidence graph). Thus, in the form of the Myhill-Nerode theorem for hypergraphs, we obtain a method to derive linear-time algorithms and to obtain indicators for intractability for hypergraph problems parameterized by incidence treewidth. In an appendix, we point out an error and a fix to the proof of the Myhill-Nerode theorem for graphs in Downey and Fellow's book on parameterized complexity., Comment: A preliminary version of this article appeared in the proceedings of ISAAC 2013. This extended and revised version contains the full proof details, more figures, and corollaries to make the application of the Myhill-Nerode theorem for hypergraphs easier in an algorithmic setting. Moreover, it provides a fix to the proof of the Myhill-Nerode theorem for graphs in the books of Downey and Fellows

Published
2012
Full Text
View/download PDF

14. Parameterizing by the Number of Numbers

Author

Fellows, Michael R., Gaspers, Serge, and Rosamond, Frances A.

Subjects
Computer Science - Data Structures and Algorithms, Computer Science - Discrete Mathematics
Abstract

The usefulness of parameterized algorithmics has often depended on what Niedermeier has called, "the art of problem parameterization". In this paper we introduce and explore a novel but general form of parameterization: the number of numbers. Several classic numerical problems, such as Subset Sum, Partition, 3-Partition, Numerical 3-Dimensional Matching, and Numerical Matching with Target Sums, have multisets of integers as input. We initiate the study of parameterizing these problems by the number of distinct integers in the input. We rely on an FPT result for ILPF to show that all the above-mentioned problems are fixed-parameter tractable when parameterized in this way. In various applied settings, problem inputs often consist in part of multisets of integers or multisets of weighted objects (such as edges in a graph, or jobs to be scheduled). Such number-of-numbers parameterized problems often reduce to subproblems about transition systems of various kinds, parameterized by the size of the system description. We consider several core problems of this kind relevant to number-of-numbers parameterization. Our main hardness result considers the problem: given a non-deterministic Mealy machine M (a finite state automaton outputting a letter on each transition), an input word x, and a census requirement c for the output word specifying how many times each letter of the output alphabet should be written, decide whether there exists a computation of M reading x that outputs a word y that meets the requirement c. We show that this problem is hard for W[1]. If the question is whether there exists an input word x such that a computation of M on x outputs a word that meets c, the problem becomes fixed-parameter tractable.

Published
2010
Full Text
View/download PDF

15. The 7th International Conference on Creative Mathematical Sciences Communication (CMSC‘24).

Author

Rosamond, Frances A.

Subjects
*SCIENTIFIC communication, *MATHEMATICS education, *QUANTUM teleportation, *QUANTUM gates, *QUANTUM computing
Abstract

The text is an invitation to the 7th International Conference on Creative Mathematical Sciences Communication (CMSC'24), which will take place from October 7-10, 2024, at the University of Trier in Germany. The conference aims to bring together mathematicians and computer scientists from around the world to explore innovative ways of communicating computational thinking and research. The conference will feature a variety of activities, including a sorting network demonstration, a math dance performance, a glass bead game, and a presentation on quantum computing. The conference proceedings will be published by Springer LNCS, and participants have the option to submit articles for publication. The CMSC conference series began in 2013 and focuses on developing hands-on computational thinking materials and activities. The conference website provides more information about the event and the submission guidelines. [Extracted from the article]

Published
2024
Full Text
View/download PDF

16. Parameterized Low-distortion Embeddings - Graph metrics into lines and trees

Author

Fellows, Michael, Fomin, Fedor, Lokshtanov, Daniel, Losievskaja, Elena, Rosamond, Frances A., and Saurabh, Saket

Subjects
Computer Science - Data Structures and Algorithms, Computer Science - Computational Complexity
Abstract

We revisit the issue of low-distortion embedding of metric spaces into the line, and more generally, into the shortest path metric of trees, from the parameterized complexity perspective.Let $M=M(G)$ be the shortest path metric of an edge weighted graph $G=(V,E)$ on $n$ vertices. We describe algorithms for the problem of finding a low distortion non-contracting embedding of $M$ into line and tree metrics. We give an $O(nd^4(2d+1)^{2d})$ time algorithm that for an unweighted graph metric $M$ and integer $d$ either constructs an embedding of $M$ into the line with distortion at most $d$, or concludes that no such embedding exists. We find the result surprising, because the considered problem bears a strong resemblance to the notoriously hard Bandwidth Minimization problem which does not admit any FPT algorithm unless an unlikely collapse of parameterized complexity classes occurs. We show that our algorithm can also be applied to construct small distortion embeddings of weighted graph metrics. The running time of our algorithm is $O(n(dW)^4(2d+1)^{2dW})$ where $W$ is the largest edge weight of the input graph. We also show that deciding whether a weighted graph metric $M(G)$ with maximum weight $W < |V(G)|$ can be embedded into the line with distortion at most $d$ is NP-Complete for every fixed rational $d \geq 2$. This rules out any possibility of an algorithm with running time $O((nW)^{h(d)})$ where $h$ is a function of $d$ alone. We generalize the result on embedding into the line by proving that for any tree $T$ with maximum degree $\Delta$, embedding of $M$ into a shortest path metric of $T$ is FPT, parameterized by $(\Delta,d)$., Comment: 19 pages, 1 Figure

Published
2008

17. A Survey on the Complexity of Flood-Filling Games

Author

Fellows, Michael R., Rosamond, Frances A., Dantas da Silva, Maise, Souza, Uéverton S., 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, Böckenhauer, Hans-Joachim, editor, Komm, Dennis, editor, and Unger, Walter, editor

Published
2018
Full Text
View/download PDF

24. On the Parameterized Complexity of Dynamic Problems with Connectivity Constraints

Author

Abu-Khzam, Faisal N., Egan, Judith, Fellows, Michael R., Rosamond, Frances A., Shaw, Peter, 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, Zhang, Zhao, editor, Wu, Lidong, editor, Xu, Wen, editor, and Du, Ding-Zhu, editor

Published
2014
Full Text
View/download PDF

25. Myhill-Nerode Methods for Hypergraphs

Author

van Bevern, René, Fellows, Michael R., Gaspers, Serge, Rosamond, Frances A., 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, Cai, Leizhen, editor, Cheng, Siu-Wing, editor, and Lam, Tak-Wah, editor

Published
2013
Full Text
View/download PDF

26. Tractable Parameterizations for the Minimum Linear Arrangement Problem

Author

Fellows, Michael R., Hermelin, Danny, Rosamond, Frances A., Shachnai, Hadas, 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, Bodlaender, Hans L., editor, and Italiano, Giuseppe F., editor

Published
2013
Full Text
View/download PDF

27. Parameterized Approximation via Fidelity Preserving Transformations

Author

Fellows, Michael R., Kulik, Ariel, Rosamond, Frances, Shachnai, Hadas, 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, Czumaj, Artur, editor, Mehlhorn, Kurt, editor, Pitts, Andrew, editor, and Wattenhofer, Roger, editor

Published
2012
Full Text
View/download PDF

28. Computer Science Unplugged and Related Projects in Math and Computer Science Popularization

Author

Bell, Tim, Rosamond, Frances, Casey, Nancy, 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, Bodlaender, Hans L., editor, Downey, Rod, editor, Fomin, Fedor V., editor, and Marx, Dániel, editor

Published
2012
Full Text
View/download PDF

29. Passion Plays: Melodramas about Mathematics

Author

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, Bodlaender, Hans L., editor, Downey, Rod, editor, Fomin, Fedor V., editor, and Marx, Dániel, editor

Published
2012
Full Text
View/download PDF

30. Train Marshalling Is Fixed Parameter Tractable

Author

Brueggeman, Leo, Fellows, Michael, Fleischer, Rudolf, Lackner, Martin, Komusiewicz, Christian, Koutis, Yiannis, Pfandler, Andreas, 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, Kranakis, Evangelos, editor, Krizanc, Danny, editor, and Luccio, Flaminia, editor

Published
2012
Full Text
View/download PDF

33. Milling a Graph with Turn Costs: A Parameterized Complexity Perspective

Author

Fellows, Mike, Giannopoulos, Panos, Knauer, Christian, Paul, Christophe, Rosamond, Frances, Whitesides, Sue, Yu, Nathan, 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, and Thilikos, Dimitrios M., editor

Published
2010
Full Text
View/download PDF

34. Well-Quasi-Orders in Subclasses of Bounded Treewidth Graphs

Author

Fellows, Michael R., Hermelin, Danny, Rosamond, Frances A., 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, Chen, Jianer, editor, and Fomin, Fedor V., editor

Published
2009
Full Text
View/download PDF

35. What Makes Equitable Connected Partition Easy

Author

Enciso, Rosa, Fellows, Michael R., Guo, Jiong, Kanj, Iyad, Rosamond, Frances, Suchý, Ondřej, 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, Chen, Jianer, editor, and Fomin, Fedor V., editor

Published
2009
Full Text
View/download PDF

36. Distortion Is Fixed Parameter Tractable

Author

Fellows, Michael R., Fomin, Fedor V., Lokshtanov, Daniel, Losievskaja, Elena, 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, Albers, Susanne, editor, Marchetti-Spaccamela, Alberto, editor, Matias, Yossi, editor, Nikoletseas, Sotiris, editor, and Thomas, Wolfgang, editor

Published
2009
Full Text
View/download PDF

37. Haplotype Inference Constrained by Plausible Haplotype Data

Author

Fellows, Michael R., Hartman, Tzvika, Hermelin, Danny, Landau, Gad M., Rosamond, Frances, Rozenberg, Liat, 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, Kucherov, Gregory, editor, and Ukkonen, Esko, editor

Published
2009
Full Text
View/download PDF

38. 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

42. Fixed-Parameter Algorithms for Kemeny Scores

Author

Betzler, Nadja, Fellows, Michael R., Guo, Jiong, Niedermeier, Rolf, Rosamond, Frances A., 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, Fleischer, Rudolf, editor, and Xu, Jinhui, editor

Published
2008
Full Text
View/download PDF

43. Leaf Powers and Their Properties: Using the Trees

Author

Fellows, Michael R., Meister, Daniel, Rosamond, Frances A., Sritharan, R., Telle, Jan Arne, 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

44. 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

45. 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

46. A Purely Democratic Characterization of W[1]

Author

Fellows, Michael, Hermelin, Danny, Müller, Moritz, 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, Grohe, Martin, editor, and Niedermeier, Rolf, editor

Published
2008
Full Text
View/download PDF

47. 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

48. On the Complexity of Some Colorful Problems Parameterized by Treewidth

Author

Fellows, Michael, Fomin, Fedor V., Lokshtanov, Daniel, Rosamond, Frances, Saurabh, Saket, Szeider, Stefan, Thomassen, Carsten, 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, Dress, Andreas, editor, Xu, Yinfeng, editor, and Zhu, Binhai, editor

Published
2007
Full Text
View/download PDF

49. Connected Coloring Completion for General Graphs: Algorithms and Complexity

Author

Chor, Benny, Fellows, Michael, Ragan, Mark A., Razgon, Igor, Rosamond, Frances, Snir, Sagi, 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, and Lin, Guohui, editor

Published
2007
Full Text
View/download PDF

50. Quadratic Kernelization for Convex Recoloring of Trees

Author

Bodlaender, Hans L., Fellows, Michael R., Langston, Michael A., Ragan, Mark A., Rosamond, Frances A., Weyer, Mark, 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, and Lin, Guohui, editor

Published
2007
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results