FEAT
发表于 2025-3-30 11:50:51
http://reply.papertrans.cn/39/3881/388032/388032_51.png
山间窄路
发表于 2025-3-30 13:43:20
Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs,+ .) time algorithm for computing the scattering number of an interval graph with . vertices and . edges, which improves the .(. .) time bound of Kratsch, Kloks and Müller. As a consequence of our two results the maximum . for which an interval graph is .-Hamilton-connected can be computed in .(. + .) time.
变形词
发表于 2025-3-30 18:22:10
http://reply.papertrans.cn/39/3881/388032/388032_53.png
透明
发表于 2025-3-30 21:45:32
https://doi.org/10.1007/978-3-642-29302-3ing these results we obtain unit-cube contact representation of several subclasses of planar graphs. We show the NP-completeness for two variants of the threshold coloring problem and describe a polynomial-time algorithm for another.
有危险
发表于 2025-3-31 01:33:24
http://reply.papertrans.cn/39/3881/388032/388032_55.png
Canopy
发表于 2025-3-31 07:24:00
Modularisierung von IT-Dienstleistungensult of independent interest: Every 3-connected planar graph with . vertices contains an induced subgraph that is outerplanar and connected and that contains at least . vertices. The proofs in the paper are constructive and give rise to .(.)-time algorithms.
Physiatrist
发表于 2025-3-31 12:28:20
Threshold-Coloring and Unit-Cube Contact Representation of Graphs,ing these results we obtain unit-cube contact representation of several subclasses of planar graphs. We show the NP-completeness for two variants of the threshold coloring problem and describe a polynomial-time algorithm for another.
Phagocytes
发表于 2025-3-31 15:10:53
Parameterized and Approximation Algorithms for the MAF Problem in Multifurcating Trees,le for general trees. We resolve this open problem by developing an .(3. .)-time parameterized algorithm for the problem on general trees. Our techniques on tree structures also lead to a polynomial-time approximation algorithm of ratio 3 for the problem, giving the first constant-ratio approximation algorithm for the problem on general trees.
Bother
发表于 2025-3-31 20:25:00
http://reply.papertrans.cn/39/3881/388032/388032_59.png
宴会
发表于 2025-3-31 22:02:30
https://doi.org/10.1007/978-1-349-12439-8 graphs. We discuss these parameters and recently established relationships between them for unweighted and undirected graphs; it turns out that all these parameters are at most constant or logarithmic factors apart from each other. We give inequalities describing their relationships and discuss consequences for some optimization problems.