Ken-ichi Kawarabayashi

According to our database1, Ken-ichi Kawarabayashi authored at least 320 papers between 2000 and 2019.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
K6 minors in 6-connected graphs of bounded tree-width.
J. Comb. Theory, Ser. B, 2019

Deterministic Edge Connectivity in Near-Linear Time.
J. ACM, 2019

Anonymising Queries by Semantic Decomposition.
CoRR, 2019

Improved Distributed Approximation to Maximum Independent Set.
CoRR, 2019

Non-zero-sum Stackelberg Budget Allocation Game for Computational Advertising.
CoRR, 2019

Are Girls Neko or Shōjo? Cross-Lingual Alignment of Non-Isomorphic Embeddings with Iterative Normalization.
CoRR, 2019

What Can Neural Networks Reason About?
CoRR, 2019

Optimal Distributed Covering Algorithms.
CoRR, 2019

Polylogarithmic approximation for Euler genus on bounded degree graphs.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Polynomial Planar Directed Grid Theorem.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Intrinsic Dimensionality Estimation within Tight Localities.
Proceedings of the 2019 SIAM International Conference on Data Mining, 2019

Non-zero-sum Stackelberg Budget Allocation Game for Computational Advertising.
Proceedings of the PRICAI 2019: Trends in Artificial Intelligence, 2019

Optimal Distributed Covering Algorithms.
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

Are Girls Neko or Shōjo? Cross-Lingual Alignment of Non-Isomorphic Embeddings with Iterative Normalization.
Proceedings of the 57th Conference of the Association for Computational Linguistics, 2019

Stochastic Submodular Maximization with Performance-Dependent Item Costs.
Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, 2019

2018
ClassiNet - Predicting Missing Features for Short-Text Classification.
TKDD, 2018

All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs.
SIAM J. Comput., 2018

Existence of outsiders as a characteristic of online communication networks.
Network Science, 2018

A new proof of the flat wall theorem.
J. Comb. Theory, Ser. B, 2018

K6 minors in large 6-connected graphs.
J. Comb. Theory, Ser. B, 2018

The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs.
J. Comb. Theory, Ser. B, 2018

Extreme-value-theoretic estimation of local intrinsic dimensionality.
Data Min. Knowl. Discov., 2018

Model-Checking on Ordered Structures.
CoRR, 2018

Optimal Distributed Weighted Set Cover Approximation.
CoRR, 2018

Tight Upper Bounds on the Crossing Number in a Minor-Closed Class.
CoRR, 2018

Parameterized Distributed Algorithms.
CoRR, 2018

Representation Learning on Graphs with Jumping Knowledge Networks.
CoRR, 2018

Causal Bandits with Propagating Inference.
CoRR, 2018

Scaling advantages of all-to-all connectivity in physical annealers: the Coherent Ising Machine vs. D-Wave 2000Q.
CoRR, 2018

ClassiNet - Predicting Missing Features for Short-Text Classification.
CoRR, 2018

A Deterministic Distributed 2-Approximation for Weighted Vertex Cover in O(log n logΔ/ log2 logΔ) Rounds.
CoRR, 2018

Adapting Local Sequential Algorithms to the Distributed Setting.
Proceedings of the 32nd International Symposium on Distributed Computing, 2018

NoSingles: a space-efficient algorithm for influence maximization.
Proceedings of the 30th International Conference on Scientific and Statistical Database Management, 2018

A Polynomial Excluded-Minor Approximation of Treedepth.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

A Deterministic Distributed 2-Approximation for Weighted Vertex Cover in O(\log N\log \varDelta /\log ^2\log \varDelta ) Rounds.
Proceedings of the Structural Information and Communication Complexity, 2018

Regret Bounds for Online Portfolio Selection with a Cardinality Constraint.
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Think Globally, Embed Locally - Locally Linear Meta-embedding of Words.
Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018

Causal Bandits with Propagating Inference.
Proceedings of the 35th International Conference on Machine Learning, 2018

Representation Learning on Graphs with Jumping Knowledge Networks.
Proceedings of the 35th International Conference on Machine Learning, 2018

Additive Non-Approximability of Chromatic Number in Proper Minor-Closed Classes.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Boosting PageRank Scores by Optimizing Internal Link Structure.
Proceedings of the Database and Expert Systems Applications, 2018

Online Regression with Partial Information: Generalization and Linear Projection.
Proceedings of the International Conference on Artificial Intelligence and Statistics, 2018

Using k-Way Co-Occurrences for Learning Word Embeddings.
Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, 2018

2017
Packing Edge-Disjoint Odd Eulerian Subgraphs Through Prescribed Vertices in 4-Edge-Connected Graphs.
SIAM J. Discrete Math., 2017

Matching Extension Missing Vertices and Edges in Triangulations of Surfaces.
Journal of Graph Theory, 2017

Coloring 3-Colorable Graphs with Less than n1/5 Colors.
J. ACM, 2017

Triangle-free graphs of tree-width t are ⌈ (t+3)/2 ⌉-colorable.
Eur. J. Comb., 2017

Think Globally, Embed Locally - Locally Linear Meta-embedding of Words.
CoRR, 2017

Using $k$-way Co-occurrences for Learning Word Embeddings.
CoRR, 2017

Polylogarithmic approximation for minimum planarization (almost).
CoRR, 2017

Additive non-approximability of chromatic number in proper minor-closed classes.
CoRR, 2017

Coarsening Massive Influence Networks for Scalable Diffusion Analysis.
Proceedings of the 2017 ACM International Conference on Management of Data, 2017

Efficient Sublinear-Regret Algorithms for Online Sparse Linear Regression with Limited Observation.
Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

An Improved Approximation Algorithm for the Subpath Planning Problem and Its Generalization.
Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, 2017

Polylogarithmic Approximation for Minimum Planarization (Almost).
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

FO Model Checking on Map Graphs.
Proceedings of the Fundamentals of Computation Theory - 21st International Symposium, 2017

Optimal Pricing for Submodular Valuations with Bounded Curvature.
Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, 2017

Scalable Algorithm for Higher-Order Co-Clustering via Random Sampling.
Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, 2017

2016
An Improved Approximation Algorithm for the Edge-Disjoint Paths Problem with Congestion Two.
ACM Trans. Algorithms, 2016

Reply trees in Twitter: data analysis and branching process models.
Social Netw. Analys. Mining, 2016

5-Connected Toroidal Graphs are Hamiltonian-Connected.
SIAM J. Discrete Math., 2016

Dynamic Influence Analysis in Evolving Networks.
PVLDB, 2016

Edge-disjoint odd cycles in 4-edge-connected graphs.
J. Comb. Theory, Ser. B, 2016

Coloring immersion-free graphs.
J. Comb. Theory, Ser. B, 2016

Non-separating subgraphs in highly connected graphs.
J. Comb. Theory, Ser. B, 2016

Packing six T-joins in plane graphs.
J. Comb. Theory, Ser. B, 2016

Optimal Pricing for Submodular Valuations with Bounded Curvature.
CoRR, 2016

Successor-Invariant First-Order Logic on Graphs with Excluded Topological Subgraphs.
CoRR, 2016

The Erdos-Posa Property for Directed Graphs.
CoRR, 2016

Maximizing Time-Decaying Influence in Social Networks.
Proceedings of the Machine Learning and Knowledge Discovery in Databases, 2016

Identifying Key Observers to Find Popular Information in Advance.
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, 2016

Adaptive Budget Allocation for Maximizing Influence of Advertisements.
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, 2016

Successor-Invariant First-Order Logic on Graphs with Excluded Topological Subgraphs.
Proceedings of the 25th EACSL Annual Conference on Computer Science Logic, 2016

Fully Dynamic Shortest-Path Distance Query Acceleration on Massive Networks.
Proceedings of the 25th ACM International Conference on Information and Knowledge Management, 2016

Expected Tensor Decomposition with Stochastic Gradient Descent.
Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, 2016

Joint Word Representation Learning Using a Corpus and a Semantic Lexicon.
Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, 2016

2015
Fixed-parameter tractability for subset feedback set problems with parity constraints.
Theor. Comput. Sci., 2015

4-connected projective-planar graphs are Hamiltonian-connected.
J. Comb. Theory, Ser. B, 2015

Subdivisions of K5 in graphs containing K2, 3.
J. Comb. Theory, Ser. B, 2015

Edge-colouring seven-regular planar graphs.
J. Comb. Theory, Ser. B, 2015

Connectivity Preserving Iterative Compaction and Finding 2 Disjoint Rooted Paths in Linear Time.
CoRR, 2015

Graph Isomorphism for Bounded Genus Graphs In Linear Time.
CoRR, 2015

The odd Hadwiger's conjecture is "almost" decidable.
CoRR, 2015

Joint Word Representation Learning using a Corpus and a Semantic Lexicon.
CoRR, 2015

Unsupervised Cross-Domain Word Representation Learning.
CoRR, 2015

Embedding Semantic Relations into Word Representations.
CoRR, 2015

The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs.
Combinatorica, 2015

The edge density of critical digraphs.
Combinatorica, 2015

Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Beyond the Euler Characteristic: Approximating the Genus of General Graphs.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

The Directed Grid Theorem.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Scalable sensor localization via ball-decomposition algorithm.
Proceedings of the 14th IFIP Networking Conference, 2015

Efficient PageRank Tracking in Evolving Networks.
Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2015

Real-Time Top-R Topic Detection on Twitter with Topic Hijack Filtering.
Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2015

Estimating Local Intrinsic Dimensionality.
Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2015

Embedding Semantic Relations into Word Representations.
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015

Budget Allocation Problem with Multiple Advertisers: A Game Theoretic View.
Proceedings of the 32nd International Conference on Machine Learning, 2015

Scalable SimRank join algorithm.
Proceedings of the 31st IEEE International Conference on Data Engineering, 2015

Towards the Graph Minor Theorems for Directed Graphs.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Unsupervised Cross-Domain Word Representation Learning.
Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing of the Asian Federation of Natural Language Processing, 2015

Lagrangian Decomposition Algorithm for Allocating Marketing Channels.
Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015

Learning Word Representations from Relational Graphs.
Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015

2014
Computing Personalized PageRank Quickly by Exploiting Graph Structures.
PVLDB, 2014

Sub-exponential graph coloring algorithm for stencil-based Jacobian computations.
J. Comput. Science, 2014

Spanning closed walks and TSP in 3-connected planar graphs.
J. Comb. Theory, Ser. B, 2014

Removable paths and cycles with parity constraints.
J. Comb. Theory, Ser. B, 2014

A connected subgraph maintaining high connectivity.
Eur. J. Comb., 2014

Existence of outsiders as a characteristic of online communication networks.
CoRR, 2014

Efficient SimRank Computation via Linearization.
CoRR, 2014

Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time.
CoRR, 2014

Beyond the Euler characteristic: Approximating the genus of general graphs.
CoRR, 2014

The Directed Grid Theorem.
CoRR, 2014

Generating Approximate Solutions to the TTP using a Linear Distance Relaxation.
CoRR, 2014

Scheduling Bipartite Tournaments to Minimize Total Travel Distance.
CoRR, 2014

Learning Word Representations from Relational Graphs.
CoRR, 2014

Minimum degree conditions for vertex-disjoint even cycles in large graphs.
Adv. Appl. Math., 2014

An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem.
Proceedings of the Symposium on Theory of Computing, 2014

Embedding and canonizing graphs of bounded genus in logspace.
Proceedings of the Symposium on Theory of Computing, 2014

Coloring 3-colorable graphs with o(n^{1/5}) colors.
Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

An Excluded Grid Theorem for Digraphs with Forbidden Minors.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Scalable similarity search for SimRank.
Proceedings of the International Conference on Management of Data, 2014

Efficient SimRank computation via linearizationPublication of this article pending inquiry.
Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2014

Network structural analysis via core-tree-decomposition Publication of this article pending inquiry.
Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2014

Optimal Budget Allocation: Theoretical Guarantee and Efficient Algorithm.
Proceedings of the 31th International Conference on Machine Learning, 2014

Fast Shortest-path Distance Queries on Road Networks by Pruned Highway Labeling.
Proceedings of the 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments, 2014

Fast and Accurate Influence Maximization on Large Networks with Pruned Monte-Carlo Simulations.
Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, 2014

Solving the Traveling Tournament Problem by Packing Three-Vertex Paths.
Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, 2014

2013
An O(log n)-Approximation Algorithm for the Edge-Disjoint Paths Problem in Eulerian Planar Graphs.
ACM Trans. Algorithms, 2013

An Approximation Algorithm for the Bipartite Traveling Tournament Problem.
Math. Oper. Res., 2013

Connectivities for k-knitted graphs and for minimal counterexamples to Hadwiger's Conjecture.
J. Comb. Theory, Ser. B, 2013

A simpler proof for the two disjoint odd cycles theorem.
J. Comb. Theory, Ser. B, 2013

Three-coloring triangle-free planar graphs in linear time
CoRR, 2013

Half-integral packing of odd cycles through prescribed vertices.
Combinatorica, 2013

Testing subdivision-freeness: property testing meets structural graph theory.
Proceedings of the Symposium on Theory of Computing Conference, 2013

More Compact Oracles for Approximate Distances in Undirected Planar Graphs.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

4-connected projective-planar graphs are hamiltonian-connected.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Packing directed cycles through a specified vertex set.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Totally odd subdivisions and parity subdivisions: Structures and Coloring.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

5-coloring K3, k-minor-free graphs: Beyond Thomassen.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

A Simple Algorithm for the Graph Minor Decomposition - Logic meets Structural Graph Theory.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

List-coloring embedded graphs.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Approximating Multi Commodity Network Design on Graphs of Bounded Pathwidth and Bounded Degree.
Proceedings of the Algorithmic Game Theory - 6th International Symposium, 2013

Model Checking for Successor-Invariant First-Order Logic on Minor-Closed Graph Classes.
Proceedings of the 28th Annual ACM/IEEE Symposium on Logic in Computer Science, 2013

Mining for Analogous Tuples from an Entity-Relation Graph.
Proceedings of the IJCAI 2013, 2013

Balancing the Traveling Tournament Problem for Weekday and Weekend Games.
Proceedings of the Twenty-Fifth Innovative Applications of Artificial Intelligence Conference, 2013

All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012
Packing Directed Circuits through Prescribed Vertices Bounded Fractionally.
SIAM J. Discrete Math., 2012

Minors in large almost-5-connected non-planar graphs.
Journal of Graph Theory, 2012

From the plane to higher surfaces.
J. Comb. Theory, Ser. B, 2012

The disjoint paths problem in quadratic time.
J. Comb. Theory, Ser. B, 2012

Fixed-parameter tractability for the subset feedback set problem and the S-cycle packing problem.
J. Comb. Theory, Ser. B, 2012

The Erdős-Pósa property for clique minors in highly connected graphs.
J. Comb. Theory, Ser. B, 2012

On the excluded minor structure theorem for graphs of large tree-width.
J. Comb. Theory, Ser. B, 2012

A linear time algorithm for the induced disjoint paths problem in planar graphs.
J. Comput. Syst. Sci., 2012

Generating Approximate Solutions to the TTP using a Linear Distance Relaxation.
J. Artif. Intell. Res., 2012

Minimally contraction-critically 6-connected graphs.
Discrete Mathematics, 2012

Linkless and Flat Embeddings in 3-Space.
Discrete & Computational Geometry, 2012

List-coloring embedded graphs
CoRR, 2012

Edge-colouring seven-regular planar graphs
CoRR, 2012

Combinatorial coloring of 3-colorable graphs
CoRR, 2012

K_6 minors in large 6-connected graphs
CoRR, 2012

K_6 minors in 6-connected graphs of bounded tree-width
CoRR, 2012

Packing cycles through prescribed vertices under modularity constraints.
Adv. Appl. Math., 2012

Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid.
Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

Edge-disjoint Odd Cycles in 4-edge-connected Graphs.
Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

Spanning closed walks and TSP in 3-connected planar graphs.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

List-coloring graphs without subdivisions and without immersions.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Erdös-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Combinatorial Coloring of 3-Colorable Graphs.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Shortest-path queries for complex networks: exploiting low tree-width outside the core.
Proceedings of the 15th International Conference on Extending Database Technology, 2012

Cliques in Odd-Minor-Free Graphs.
Proceedings of the Eighteenth Computing: The Australasian Theory Symposium, 2012

The Linear Distance Traveling Tournament Problem.
Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, 2012

2011
Three-coloring triangle-free planar graphs in linear time.
ACM Trans. Algorithms, 2011

An Improved Algorithm for the Half-Disjoint Paths Problem.
SIAM J. Discrete Math., 2011

Graph Algorithm and Combinatorial Optimization (NII Shonan Meeting 2011-1).
NII Shonan Meet. Rep., 2011

2- and 3-factors of graphs on surfaces.
Journal of Graph Theory, 2011

Non-separating subgraphs after deleting many disjoint paths.
J. Comb. Theory, Ser. B, 2011

The 2-extendability of 5-connected graphs on surfaces with large representativity.
J. Comb. Theory, Ser. B, 2011

Packing cycles through prescribed vertices.
J. Comb. Theory, Ser. B, 2011

Scheduling Bipartite Tournaments to Minimize Total Travel Distance.
J. Artif. Intell. Res., 2011

A multi-round generalization of the traveling tournament problem and its application to Japanese baseball.
European Journal of Operational Research, 2011

Hamilton cycles in 4-connected troidal triangulations.
Electronic Notes in Discrete Mathematics, 2011

High connectivity keeping connected subgraph.
Electronic Notes in Discrete Mathematics, 2011

Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus, and Minor-Free Graphs
CoRR, 2011

Minimum k-way cut of bounded size is fixed-parameter tractable
CoRR, 2011

Toughness of Ka,t-Minor-Free Graphs.
Electr. J. Comb., 2011

The Disjoint Paths Problem: Algorithm and Structure.
Proceedings of the WALCOM: Algorithms and Computation - 5th International Workshop, 2011

A simpler algorithm and shorter proof for the graph minor decomposition.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Breaking o(n1/2)-approximation algorithms for the edge-disjoint paths problem with congestion two.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Finding topological subgraphs is fixed-parameter tractable.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Contraction decomposition in h-minor-free graphs and algorithmic applications.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

The Graph Minor Algorithm with Parity Conditions.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

The Multi-Round Balanced Traveling Tournament Problem.
Proceedings of the 21st International Conference on Automated Planning and Scheduling, 2011

The Inter-League Extension of the Traveling Tournament Problem and its Application to Sports Scheduling.
Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011

2010
A simple algorithm for 4-coloring 3-colorable planar graphs.
Theor. Comput. Sci., 2010

Star Coloring and Acyclic Coloring of Locally Planar Graphs.
SIAM J. Discrete Math., 2010

Dominating sets in triangulations on surfaces.
Journal of Graph Theory, 2010

Contractible Small Subgraphs in k-connected Graphs.
Graphs and Combinatorics, 2010

A note on traversing specified vertices in graphs embedded with large representativity.
Discrete Mathematics, 2010

Finding topological subgraphs is fixed-parameter tractable
CoRR, 2010

Double-Critical Graphs and Complete Minors.
Electr. J. Comb., 2010

Algorithms for finding an induced cycle in planar graphs.
Combinatorica, 2010

Non-separating even cycles in highly connected graphs.
Combinatorica, 2010

Immersing small complete graphs.
Ars Math. Contemp., 2010

A shorter proof of the graph minor algorithm: the unique linkage theorem.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Odd cycle packing.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

An (almost) Linear Time Algorithm for Odd Cyles Transversal.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Recognizing a Totally Odd K4-subdivision, Parity 2-disjoint Rooted Paths and a Parity Cycle Through Specified Elements.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

The Edge Disjoint Paths Problem in Eulerian Graphs and 4-edge-connected Graphs.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Decomposition, Approximation, and Coloring of Odd-Minor-Free Graphs.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Message Duplication Reduction in Dense Mobile Social Networks.
Proceedings of the 19th International Conference on Computer Communications and Networks, 2010

A Separator Theorem in Minor-Closed Classes.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Linkless and flat embeddings in 3-space and the unknot problem.
Proceedings of the 26th ACM Symposium on Computational Geometry, 2010

Improved Algorithm for the Half-Disjoint Paths Problem.
Proceedings of the Approximation, 2010

An O(logn)-Approximation Algorithm for the Disjoint Paths Problem in Eulerian Planar Graphs and 4-Edge-Connected Planar Graphs.
Proceedings of the Approximation, 2010

2009
6-Critical Graphs on the Klein Bottle.
SIAM J. Discrete Math., 2009

Decomposing a planar graph of girth 5 into an independent set and a forest.
J. Comb. Theory, Ser. B, 2009

Removable cycles in non-bipartite graphs.
J. Comb. Theory, Ser. B, 2009

N-flips in even triangulations on surfaces.
J. Comb. Theory, Ser. B, 2009

Note on coloring graphs without odd-Kk-minors.
J. Comb. Theory, Ser. B, 2009

Linear connectivity forces large complete bipartite minors.
J. Comb. Theory, Ser. B, 2009

Linear connectivity forces large complete bipartite minors: [J. Combin. Theory Ser. B Vol. 99(2)]
J. Comb. Theory, Ser. B, 2009

On the number of 4-contractible edges in 4-connected graphs.
J. Comb. Theory, Ser. B, 2009

Bounding the Size of Equimatchable Graphs of Fixed Genus.
Graphs and Combinatorics, 2009

Disjoint Even Cycles Packing.
Electronic Notes in Discrete Mathematics, 2009

List-coloring graphs without K4, k-minors.
Discrete Applied Mathematics, 2009

Note on non-separating and removable cycles in highly connected graphs.
Discrete Applied Mathematics, 2009

Highly parity linked graphs.
Combinatorica, 2009

Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction.
Algorithmica, 2009

Hadwiger's conjecture is decidable.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Algorithms for finding an induced cycle in planar graphs and bounded genus graphs.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

A nearly linear time algorithm for the half integral parity disjoint paths packing problem.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

List-color-critical graphs on a fixed surface.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Additive approximation algorithms for list-coloring minor-closed class of graphs.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Three-coloring triangle-free planar graphs in linear time.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs.
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Planarity Allowing Few Error Vertices in Linear Time.
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008
K6-Minors in Triangulations on the Klein Bottle.
SIAM J. Discrete Math., 2008

Nonseparating Induced Cycles Consisting of Contractible Edges in k-Connected Graphs.
SIAM J. Discrete Math., 2008

Contractible elements in k-connected graphs not containing some specified graphs.
Journal of Graph Theory, 2008

A weaker version of Lovász' path removal conjecture.
J. Comb. Theory, Ser. B, 2008

Connectivity keeping edges in graphs with large minimum degree.
J. Comb. Theory, Ser. B, 2008

Locally planar graphs are 5-choosable.
J. Comb. Theory, Ser. B, 2008

On the matching extendability of graphs in surfaces.
J. Comb. Theory, Ser. B, 2008

N-Flips in even triangulations on surfaces.
Electronic Notes in Discrete Mathematics, 2008

Six-Critical Graphs on the Klein Bottle.
Electronic Notes in Discrete Mathematics, 2008

Fractional coloring and the odd Hadwiger's conjecture.
Eur. J. Comb., 2008

Long cycles in graphs without hamiltonian paths.
Discrete Mathematics, 2008

Contractible edges in minimally k-connected graphs.
Discrete Mathematics, 2008

A Weakening of the Odd Hadwiger's Conjecture.
Combinatorics, Probability & Computing, 2008

Graph and map isomorphism and all polyhedral embeddings in linear time.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

A nearly linear time algorithm for the half integral disjoint paths packing.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

The Induced Disjoint Paths Problem.
Proceedings of the Integer Programming and Combinatorial Optimization, 2008

An Improved Algorithm for Finding Cycles Through Elements.
Proceedings of the Integer Programming and Combinatorial Optimization, 2008

Approximating List-Coloring on a Fixed Surface.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

A Simpler Linear Time Algorithm for Embedding Graphs into an Arbitrary Surface and the Genus of Graphs of Bounded Tree-Width.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Improved upper bounds on the crossing number.
Proceedings of the 24th ACM Symposium on Computational Geometry, 2008

2007
Independence number and clique minors.
Journal of Graph Theory, 2007

Extremal results for rooted minor problems.
Journal of Graph Theory, 2007

A relaxed Hadwiger's Conjecture for list colorings.
J. Comb. Theory, Ser. B, 2007

On the connectivity of minimum and minimal counterexamples to Hadwiger's Conjecture.
J. Comb. Theory, Ser. B, 2007

2-Connected spanning subgraphs with low maximum degree in locally planar graphs.
J. Comb. Theory, Ser. B, 2007

Some Recent Progress and Applications in Graph Minor Theory.
Graphs and Combinatorics, 2007

Chords of longest circuits in locally planar graphs.
Eur. J. Comb., 2007

Chvátal Erdós condition and 2-factors with a specyfied number of components.
Discussiones Mathematicae Graph Theory, 2007

The Erdos-Pósa property for vertex- and edge-disjoint odd cycles in graphs on orientable surfaces.
Discrete Mathematics, 2007

Some remarks on the odd hadwiger's conjecture.
Combinatorica, 2007

Computing crossing number in linear time.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Half integral packing, Erdős-Posá-property and graph minors.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2006
Domination in a graph with a 2-factor.
Journal of Graph Theory, 2006

Non-zero disjoint cycles in highly connected group labelled graphs.
J. Comb. Theory, Ser. B, 2006

A pair of forbidden subgraphs and perfect matchings.
J. Comb. Theory, Ser. B, 2006

On Sufficient Degree Conditions for a Graph to be k-linked.
Combinatorics, Probability & Computing, 2006

Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction.
Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

2005
Detecting even holes.
Journal of Graph Theory, 2005

Graph minors and linkages.
Journal of Graph Theory, 2005

Improvements of the theorem of Duchet and Meyniel on Hadwiger's conjecture.
J. Comb. Theory, Ser. B, 2005

Vertices of Degree 5 in a Contraction Critically 5-connected Graph.
Graphs and Combinatorics, 2005

Non-zero disjoint cycles in highly connected group labeled graphs.
Electronic Notes in Discrete Mathematics, 2005

On the structure of k-connected graphs without Kk-minor.
Eur. J. Comb., 2005

Acute triangles in 4-connected maximal plane graphs.
Discrete Mathematics, 2005

Existence of two disjoint long cycles in graphs.
Discrete Mathematics, 2005

Any 7-Chromatic Graphs Has K7 Or K4, 4 As A Minor.
Combinatorica, 2005

Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004
Orientable and Nonorientable Genera for Some Complete Tripartite Graphs.
SIAM J. Discrete Math., 2004

K-linked graphs with girth condition.
Journal of Graph Theory, 2004

Vertex-disjoint cycles containing specified vertices in a bipartite graph.
Journal of Graph Theory, 2004

Cycles through a prescribed vertex set in N-connected graphs.
J. Comb. Theory, Ser. B, 2004

A theorem on paths in locally planar triangulations.
Eur. J. Comb., 2004

Vertex-disjoint copies of K4-.
Discussiones Mathematicae Graph Theory, 2004

Rooted minor problems in highly connected graphs.
Discrete Mathematics, 2004

2003
2-connected 7-coverings of 3-connected graphs on surfaces.
Journal of Graph Theory, 2003

Subgraphs of graphs on surfaces with high representativity .
J. Comb. Theory, Ser. B, 2003

On two equimatchable graph classes.
Discrete Mathematics, 2003

Covering vertices of a graph by k disjoint cycles.
Discrete Mathematics, 2003

Vertices of degree 6 in a contraction critically 6-connected graph.
Discrete Mathematics, 2003

Some forbidden subgraph conditions for a graph to have a k-contractible edge.
Discrete Mathematics, 2003

Cycles having the same modularity and removable edges in 2-connected graphs.
Discrete Mathematics, 2003

2002
Hamiltonian cycles in n-extendable graphs.
Journal of Graph Theory, 2002

Path factors in cubic graphs.
Journal of Graph Theory, 2002

K4--factor in a graph.
Journal of Graph Theory, 2002

One or Two Disjoint Circuits Cover Independent Edges: Lovász-Woodall Conjecture.
J. Comb. Theory, Ser. B, 2002

Contractible Edges and Triangles in k-Connected Graphs.
J. Comb. Theory, Ser. B, 2002

Nonseparating Induced Cycles Consisting of Contractible Edges in k-Connected Graphs.
Electronic Notes in Discrete Mathematics, 2002

Contractible edges in minimally k-connected graphs.
Electronic Notes in Discrete Mathematics, 2002

On separable self-complementary graphs.
Discrete Mathematics, 2002

Graph partition into paths containing specified vertices.
Discrete Mathematics, 2002

On a hamiltonian cycle in which specified vertices are not isolated.
Discrete Mathematics, 2002

Path factors in claw-free graphs.
Discrete Mathematics, 2002

F-factor and Vertex-disjoint F in a graph.
Ars Comb., 2002

Contractible Edges and Bowties in a k-Connected Graph.
Ars Comb., 2002

2001
Vertices of degree 6 in a 6-contraction critical graph.
Electronic Notes in Discrete Mathematics, 2001

Hamiltonian cycles in n-factor-critical graphs.
Discrete Mathematics, 2001

Note on k-contractible edges in k-connected graphs.
Australasian J. Combinatorics, 2001

Vertex-disjoint cycles containing specified edges in a bipartite graph.
Australasian J. Combinatorics, 2001

2000
Relative Length of Longest Path and Longest Cycle.
Electronic Notes in Discrete Mathematics, 2000

Geometric Transformations in Plane Triangulations.
Proceedings of the Discrete and Computational Geometry, Japanese Conference, 2000


  Loading...