Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs

Autor: Broersma, Haitze J., Fiala, Jiri, Golovach, Petr A., Kaiser, Tomas, Paulusma, Daniël, Proskurowski, Andrzej, Brandstädt, Andreas, Jansen, Klaus, Reischuk, Rüdiger

Publikováno v: Brandstädt, Andreas & Jansen, Klaus & Reischuk, Rüdige (Eds.). (2013). Graph-theoretic concepts in computer science : 39th International Workshop, WG 2013, 19-21 June 2013, Lübeck, Germany ; revised papers. Berlin, Heidelberg: Springer, pp. 127-138, Lecture notes in computer science(8165)
Graph-Theoretic Concepts in Computer Science: 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers, 127-138
STARTPAGE=127;ENDPAGE=138;TITLE=Graph-Theoretic Concepts in Computer Science
Graph-Theoretic Concepts in Computer Science ISBN: 9783642450426
WG

We show that for all k ≤ − 1 an interval graph is − (k + 1)-Hamilton-connected if and only if its scattering number is at most k. We also give an O(n + m) time algorithm for computing the scattering number of an interval graph with n vertices a

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4b2b5cdf5381f9c50102ec29a843c3bf
https://doi.org/10.1007/978-3-642-45043-3_12

Pairs of forbidden induced subgraphs for homogeneously traceable graphs

Autor: Li, Binlong, Broersma, Haitze J., Zhang, Shenggui

Publikováno v: Discrete mathematics, 312(18), 2800-2818. Elsevier

A graph G is called homogeneously traceable if for every vertex v of G, G contains a Hamilton path starting from v. For a graph H, we say that G is H-free if G contains no induced subgraph isomorphic to H. For a family H of graphs, G is called H-free

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6e1abac35e188d1c539651b178a44747
https://doi.org/10.1016/j.disc.2012.05.018

Upper bounds and algorithms for parallel knock-out numbers

Autor: Broersma, Haitze J., Johnson, Matthew, Paulusma, Daniël, Stewart, Iain A.

Publikováno v: Theoretical computer science, 410(14):10.1016/j.tcs.2008.03.024, 1319-1327. Elsevier
Theoretical computer science, 2009, Vol.410(14), pp.1319-1327 [Peer Reviewed Journal]

We study parallel knock-out schemes for graphs. These schemes proceed in rounds in each of which each surviving vertex simultaneously eliminates one of its surviving neighbours; a graph is reducible if such a scheme can eliminate every vertex in the

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::eb8d2e45144ca53f0820fb4581fb6bd6

Tutte sets in graphs I: Maximal tutte sets and D-graphs

Autor: Bauer, D., Broersma, Haitze J., Morgana, A., Schmeichel, E.

Publikováno v: Journal of graph theory, 55(SINTEF A13/4):10.1002/jgt.20243, 343-358. Wiley-Liss Inc.

A well-known formula of Tutte and Berge expresses the size of a maximum matching in a graph $G$ in terms of what is usually called the deficiency of $G$. A subset $X$ of $V(G)$ for which this deficiency is attained is called a Tutte set of $G$. While

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0fe23a8c15b596f51dec56f6b01d8f5e
http://eprints.eemcs.utwente.nl/secure2/10335/01/fulltext.pdf

Computational matter: evolving computational solutions in materials

Autor: Miller, Julian F., Broersma, Haitze J., Silva, Sara

Publikováno v: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, GECCO Companion 2015, 769-770
STARTPAGE=769;ENDPAGE=770;TITLE=Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, GECCO Companion 2015
GECCO (Companion)

Natural Evolution has been exploiting the physical properties of matter since life first appeared on earth. Evolution-in-materio (EIM) attempts to program matter so that computational problems can be solved. The beauty of this approach is that artifi

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::fa7913a27b182d4c2feb90fb7f97e38b
https://doi.org/10.1145/2739482.2764939