Zobrazeno 1 - 10
of 75
pro vyhledávání: '"Martin Fürer"'
Autor:
Martin Fürer
Publikováno v:
Electronic Proceedings in Theoretical Computer Science, Vol 9, Iss Proc. DCM 2009, Pp 49-53 (2009)
This paper studies two issues related to the paper on Computing by Self-reproduction: Autopoietic Automata by Jiri Wiedermann. It is shown that all results presented there extend to deterministic computations. In particular, nondeterminism is not nee
Externí odkaz:
https://doaj.org/article/5b785bf928ef4399bcd50274bb43479c
Publikováno v:
Journal of Computational Geometry, Vol 3, Iss 1 (2012)
A ball graph is an intersection graph of a set of balls with arbitrary radii. Given a real numbert>1, we say that a subgraph G' of a graph G is a t-spanner of G, if for every pair of verticesu,v in G, there exists a path in G' of length at most t tim
Externí odkaz:
https://doaj.org/article/68620becf4d44d0a803652b44e50ca8f
Publikováno v:
Linear Algebra and its Applications. 560:56-85
Finding a diagonal matrix congruent to $A - cI$ for constants $c$, where $A$ is the adjacency matrix of a graph $G$ allows us to quickly tell the number of eigenvalues in a given interval. If $G$ has clique-width $k$ and a corresponding $k$-expressio
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::14118780c2f72c4ee378e93098e4bd1c
https://doi.org/10.1016/j.laa.2018.09.015
https://doi.org/10.1016/j.laa.2018.09.015
Autor:
Mahdi Belbasi, Martin Fürer
Publikováno v:
Combinatorial Optimization and Applications ISBN: 9783030926809
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ded054ad5b06f2fdf82cad89d76c76f7
https://doi.org/10.1007/978-3-030-92681-6_23
https://doi.org/10.1007/978-3-030-92681-6_23
Autor:
Mahdi Belbasi, Martin Fürer
Publikováno v:
WALCOM: Algorithms and Computation ISBN: 9783030682101
WALCOM
WALCOM
We present a new approximation algorithm for the treewidth problem which constructs a corresponding tree decomposition as well. Our algorithm is a faster variation of Reed’s classical algorithm. For the benefit of the reader, and to be able to comp
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::0b32619540d4c74203956e4be6d48cff
https://doi.org/10.1007/978-3-030-68211-8_14
https://doi.org/10.1007/978-3-030-68211-8_14
Autor:
Martin Fürer, Huiwen Yu
Publikováno v:
Theory of Computing Systems. 61:283-304
Dynamic programming is widely used for exact computations based on tree decompositions of graphs. However, the space complexity is usually exponential in the treewidth. We study the problem of designing efficient dynamic programming algorithms based
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::df663454b2ad8f3125280030bb10062b
https://doi.org/10.1007/s00224-017-9751-3
https://doi.org/10.1007/s00224-017-9751-3
Autor:
Martin Fürer, Mahdi Belbasi
Publikováno v:
Computer Science – Theory and Applications ISBN: 9783030199548
CSR
CSR
An NP-hard graph problem may be intractable for general graphs but it could be efficiently solvable using dynamic programming for graphs with bounded treewidth. Employing dynamic programming on a tree decomposition usually uses exponential space. In
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5fa62ee1429332aa404c979d6141facb
https://doi.org/10.1007/978-3-030-19955-5_4
https://doi.org/10.1007/978-3-030-19955-5_4
Publikováno v:
LATIN 2018: Theoretical Informatics ISBN: 9783319774039
LATIN
LATIN
It is shown that if G has clique-width k, and a corresponding tree decomposition is known, then a diagonal matrix congruent to \(A - cI\) for constants c, where A is the adjacency matrix of the graph G of order n, can be computed in time \(O(k^2 n)\)
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::17869209206d6c9521daeaeb197532a8
https://doi.org/10.1007/978-3-319-77404-6_35
https://doi.org/10.1007/978-3-319-77404-6_35
Autor:
Martin Fürer, Panagiotis Cheilaris, Christos Nomikos, Euripides Markou, Nikolaos Papaspyrou, Eleni Bakali, Dimitris Fotakis, Katerina Potika, Costas D. Koutras, Christos H. Papadimitriou, Aris Pagourtzis
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783319575858
CIAC
CIAC
This year we are celebrating the 70th birthday of Stathis! We take this chance to recall some of his remarkable contributions to Computer Science.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1afd97f73302facf4c5e8084a468de72
https://doi.org/10.1007/978-3-319-57586-5_39
https://doi.org/10.1007/978-3-319-57586-5_39
Autor:
Martin Fürer
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783319575858
CIAC
CIAC
The classical Weisfeiler-Lehman method WL[2] uses edge colors to produce a powerful graph invariant. It is at least as powerful in its ability to distinguish non-isomorphic graphs as the most prominent algebraic graph invariants. It determines not on
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e9f3f7ad778a93ea04ec68f0a3be8978
https://doi.org/10.1007/978-3-319-57586-5_22
https://doi.org/10.1007/978-3-319-57586-5_22