A5062803495- Advanced Graph Theory Research
- Complexity and Algorithms in Graphs
- Optimization and Search Problems
- VLSI and FPGA Design Techniques
- Interconnection Networks and Systems
- Education, Psychology, and Social Research
- Algorithms and Data Compression
- semigroups and automata theory
- Graph Labeling and Dimension Problems
- Game Theory and Voting Systems
- Computational Geometry and Mesh Generation
- Internet Traffic Analysis and Secure E-voting
- Game Theory and Applications
- DNA and Biological Computing
- Graph Theory and Algorithms
- Limits and Structures in Graph Theory
- Opportunistic and Delay-Tolerant Networks
- Data Management and Algorithms
- Opinion Dynamics and Social Influence
- Network Packet Processing and Optimization
- Complex Network Analysis Techniques
- graph theory and CDMA systems
- Merger and Competition Analysis
- Ancient and Medieval Archaeology Studies
- Privacy-Preserving Technologies in Data
Czech Technical University in Prague
2015-2024
Technische Universität Berlin
2012-2021
Technical services for air protection Prague (Czechia)
2015
Eindhoven University of Technology
2014
Saarland University
2011-2012
Charles University
2009-2010
Assume that each of n voters may or not approve m issues. If an agent (the lobby) influence up to k voters, then the central question NP-hard Lobbying problem is whether lobby can choose be influenced so as a result issue gets majority approvals. This modeled simple matrix modification problem: Can one replace rows binary x m-matrix by all-1 such column in resulting has 1s? Significantly extending on previous work showed parameterized intractability (W[2]-completeness) with respect number...
We start a systematic parameterized computational complexity study of three NP-hard network design problems on arc-weighted directed graphs: Steiner tree, strongly connected subgraph, and network. investigate their complexities with respect to the parameterizations: "number terminals," "an upper bound size connecting network," combination these two. achieve several hardness results as well some fixed-parameter tractability results, in this way extending previous Feldman Ruhl [SIAM J....
Abstract Motivated by the recent rapid growth of research for algorithms to cluster multi-layer and temporal graphs, we study extensions classical Cluster Editing problem. In Multi-Layer receive a set graphs on same vertex set, called layers aim transform all into (disjoint unions cliques) that differ only slightly. More specifically, want mark at most d vertices each layer graph using k edge additions or deletions per so that, if remove marked vertices, obtain in layers. Temporal sequence...
We present several polynomial-time algorithms for c-planarity testing cluster hierarchy C containing clusters of size at most three. The main result is an O(|C| + n)-time algorithm three on a cycle. then generalized to special class Eulerian graphs, namely graphs obtained from 3-connected planar graph fixed k by multiplying and subdividing edges. An O(3 · presented. further give general graphs. Submitted: December 2007 Reviewed: November 2008 Revised: February 2009 Accepted: August Final:...
We extend work by Christian et al. [Review of Economic Design 2007] on lobbying in multiple referenda first providing a more fine-grained analysis the computational complexity NP-complete Lobbying problem. Herein, given binary matrix, columns represent issues to vote and rows correspond voters making each issue. An issue is approved if majority votes has 1 corresponding column. The goal get all modifying minimum number all-1-rows. In our multivariate analysis, we present holistic view nature...
We study the parameterized complexity of directed variant classical Steiner Tree problem on various classes sparse graphs. While by number terminals is well understood, not much known about parameterization nonterminals in solution tree. All that for this both and undirected versions are W[2]-hard general graphs hence unlikely to be fixed parameter tractable (FPT). The becomes FPT when restricted such as planar graphs, but techniques used show result break down In article we precisely chart...
The NP-hard Subset Interconnection Design problem, also known as Minimum Topic-Connected Overlay, is motivated by numerous applications including the design of scalable overlay networks and vacuum systems. It has input a finite set $V$ collection subsets $V_1, V_2, \ldots, V_m \subseteq V$, asks for minimum-cardinality edge $E$ such that graph $G=(V,E)$ all induced subgraphs $G[V_1], G[V_2], G[V_m]$ are connected. We study in context polynomial-time data reduction rules preserve possibility...
Motivated by the recent rapid growth of research for algorithms to cluster multi-layer and temporal graphs, we study extensions classical Cluster Editing problem. In Multi-Layer receive a set graphs on same vertex set, called layers aim transform all into (disjoint unions cliques) that differ only slightly. More specifically, want mark at most d vertices each layer graph using k edge additions or deletions per so that, if remove marked vertices, obtain in layers. Temporal sequence...