Thomas M. Kratzke

dblp:31/6364 · DBLP profile ↗
← Back
4ranked-venue papers
3as first author
1since 2021 · last 2025
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Databases, data management, data science and information retrieval · 2 · 1 first-authorTheory of computation · 2 · 2 first-author · 1 since 2021
YearPublicationVenuePosition
2025 The total interval number of a graph, III: Tree-like graphs
Thomas M. Kratzke, Douglas B. West
Discret. Appl. Math.1
2011 Search analysis for the underwater wreckage of Air France Flight 447
Lawrence D. Stone, Colleen M. Keller, Thomas M. Kratzke, Johan Strümpfer
FUSION3
2010 Search and Rescue Optimal Planning System
Thomas M. Kratzke, Lawrence D. Stone, John R. Frost
FUSION1
1996 The Total Interval Number of a Graph II: Trees and Complexity
abstract
A multiple-interval representation of a simple graph G assigns each vertex a union of disjoint real intervals so that vertices are adjacent if and only if their assigned sets intersect. The total interval number$I(G)$ is the minimum of the total number of intervals used in such a representation of G. For triangle-free graphs, $I(G) = | E(G) |+t(G)$, where $t(G)$ is the minimum number of pairwise edge-disjoint trails that together contain an endpoint of each edge. This yields the NP-completeness of testing $I(G) = | E(G) | + 1$ (even for triangle-free 3-regular planar graphs) and an alternative proof that HAMILTONIAN CYCLE is NP-complete for line graphs. It also yields a linear-time algorithm to compute $I(G)$ for trees and a characterization of the trees requiring $| E(G) | + t$ intervals for fixed t. Further corollaries include the Aigner-Andreae bound of $I(G) \leq \lfloor {(5n - 3)/4} \rfloor $ for n-vertex trees (achieved by subdividing every edge of a star), a characterization of the extremal trees, and a shorter proof of the extremal bound $\lfloor {(5m + 2)/4} \rfloor $ for connected graphs.
Thomas M. Kratzke, Douglas B. West
SIAM J. Discret. Math.1